题目链接：
http://poj.org/problem?id=2524
题意： n个人，m对人宗教相同，输出一共有多少个不同的宗教。
代码如下：
#include<iostream>
#include<cstdio>
using namespace std; #define M 500100
int par[M];
int h[M];
int n, m; void init(int a)
{
for(int i = 1; i <= a; i++)
{
par[i] = i;
h[i] = 0;
}
}
int Find(int a)
{
if(par[a] != a)
{
return par[a] = Find(par[a]);
}
else return a;
}
void Union(int a,int b)
{
a = Find(a);
b = Find(b);
if(a == b) return;
else
{
if(h[a] > h[b]) par[b] = a;
else
{
if(h[a] == h[b]) h[b]++;
par[a] = b;
}
}
} int main()
{
int cases = 1;
while(scanf("%d%d",&n,&m) == 2)
{
if(n == 0) break;
init(n);
int Count = 0;
for(int i = 0; i < m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
Union(a,b);
}
for(int i = 1; i <= n; i++)
{
if(par[i] == i) Count++; //自己是根节点的是一类宗教
}
cout<<"Case "<<cases++<<": "<<Count<<endl;
}
return 0;
}
之前wa了好多次，原因是定义了一个visit[ ]数组来记录visit[ par[i] ]有没有被访问来记录宗教数，但忽略了节点可能不是直接连在根节点上的情况。。。Orz。。。。
作者：u011652573 发表于2014-3-3 19:27:19 原文链接
阅读：45 评论：0 查看评论