[Uva 10608 ]Friends

方法 : Disjaint Sat

	#include<iostream>
	#include<cstdio>
	using namespace std;
	int p[100001],N,sum[100000];
	//陣列初始化
	void init(){
	for(int k=1;k<=N;k++)
	{
	p[k] = k;
	sum[k] = 0;
	}
	}
	//尋找父親
	int Find(int x)
	{
	if (x == p[x]) return x;
	p[x] = Find(p[x]);//順手作壓縮
	return p[x];
	}
	//將x y連起來
	void Union(int x,int y){
	int fx = Find(x);
	int fy = Find(y);
	p[fx] = fy;//x的root連在y的root之屁屁上
	}
	int main(){
	int T,M,i,j;
	char ch;
	scanf("%d",&T);//輸入幾筆測資
	while(T--){
	scanf("%d %d",&N,&M);//輸入幾個住戶 和幾筆關係
	init();//陣列初始化
	while(M--){
	scanf("%d %d",&i,&j);//輸入關係並相連
	Union(i,j);
	}
	for(i=N;i>=0;i--){
	sum[Find(i)]++;//將關係相同root++ 若Find[i]==6 then sum[6]++
	}
	j = 0;
	for(i=N;i>=0;i--){
	j = max(sum[i],j);//輸出最多關係的關係人數
	}
	cout<<j<<endl;
	}
	}

view raw gistfile1.cpp hosted with ❤ by GitHub