之前這個問題用深度優先搜索做的。。耗時很長，很顯然這是一個并查集的題目：
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector <int> a[50001];
int n,m,col;
bool v[50001];
void dfs(int k)
{
int i,j;
v[k]=1;
for(i=0;i<a[k].size();i++)
if(v[a[k][i]]==0)dfs(a[k][i]);
}
int main()
{
int i,j,p,q,cn=0;
while(scanf("%d %d",&n,&m),n||m)
{
for(i=1;i<=n;i++)a[i].clear(),v[i]=0;
for(i=0;i<m;i++)scanf("%d %d",&p,&q),a[p].push_back(q),a[q].push_back(p);
col=0;
for(i=1;i<=n;i++)if(v[i]==0)dfs(i),col++;
printf("Case %d: %d\n",++cn,col);
}
return 0;
}
并查集版本：
#include <iostream>
using namespace std;
#define MAXN 500001
struct
{
int parent;
int rank;
}UFS[MAXN]; //UnionFindSet UFS
//其中Parent為正數時表示該節點的父節點下標，為負數時表示該節點為一個根節點，其絕對值為該集合包含的節點總數。
//rank表示權值，在不同問題中有不同的含義。
void MakeSet(int N) /* 初始化 */
{
int i;
for(i=0;i<=N;i++) //額外增加一位，從0開始可以從1開始也可以
{
UFS[i].parent=-1; /* 開始每個節點單獨構成一個集合 */
UFS[i].rank=0; /* 權值視具體情況付初值 */
}
}
int Root(int x) /* 查找包含接點x的集合的根節點 */
{
int i=x,temp;
while(UFS[i].parent>0)
i=UFS[i].parent;
while(i!=x) /* 壓縮路徑以提高以后檢索效率 */
{
temp=UFS[x].parent;
UFS[x].parent=i; //直接將x的祖先命為根節點
x=temp; //繼續處理x的原祖先
}
return i;
}
void Union1(int a,int b) /* 合并a和b所在的集合 */
{
int fa,fb;
fa=Root(a);
fb=Root(b);
if(fa==fb) return;
if(UFS[fa].parent<UFS[fb].parent) /* 始終將較小樹作為較大樹的子樹 */
{
UFS[fa].parent+=UFS[fb].parent;
UFS[fb].parent=fa;
}
else
{
UFS[fb].parent+=UFS[fa].parent;
UFS[fa].parent=fb;
}
}
void Union2(int a, int b) //將rank較大的作為父節點
{
int x = Root(a), y = Root(b);
if( x == y ) return ;
if( UFS[x].rank > UFS[y].rank ) UFS[y].parent = x;
else{
UFS[x].parent = y;
if( UFS[x].rank == UFS[y].rank ) UFS[y].rank++;
}
}
int main()
{
int N, M, a, b;
int nCases = 1;
while(scanf("%d %d", &N, &M) && (M||N))
{
MakeSet(N);
for(int i=1; i<=M; ++i)
{
scanf("%d %d", &a, &b);
a = Root(a);
b = Root(b);
//如果a,b不在同一個集合，則合并
if(a != b)
{
N--;
Union2(a, b);
}
}
printf("Case %d: %d\n", nCases++, N);
}
return 0;
}
今天明天總結一下并查集的相關知識吧！