新浪博客

CF 91C Ski Base图中任意时刻有多少个环

2011-10-08 15:59阅读:
题目描述:
n个点,m条边,每加一条边,问当前图中有多少个不同的环。
解题报告:
直接上结论:
用并查集维护
如果加边的两点已经是联通的,ans = (ans * 2 + 1) % mod
否则并查集相连即可。
代码如下;
#include<iostream>

#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
#define SIZE 100005
#define mod 1000000009
int fa[SIZE], ans;
int find(int id)
{
if (fa[id] == -1) return id;
return fa[id] = find(fa[id]);
}
void un(int a, int b)
{
int aa = find(a), bb = find(b);
if (aa == bb) ans = (ans * 2 + 1) % mod;
else fa[aa] = bb;
}
int main()
{
int n, m;scanf('%d%d', &n, &m); ans = 0;
memset(fa, -1, sizeof(fa));
while(m--)
{
int a, b;scanf('%d%d', &a, &b);
un(a, b);
printf('%d', ans);
}
return 0;
}

我的更多文章

下载客户端阅读体验更佳

APP专享