UVA - 10608-Friends(並查集）

題目:UVA - 10608-Friends

題目大意：給定n個人，和m個關系，m個關系代表誰和誰認識之類的，求這樣的關系中，朋友圈人數最多的人數。

解題思路：這題用並查集來判斷這兩個人是否屬於同一個朋友圈，剛開始每個人自己形成一個朋友圈，所以朋友圈人數為1，然後每碰到一個關系就判斷這兩個人是否屬於同一個朋友圈，如果不是，就把其中一個的f【t】（t為這個圈子的根）改為另一個朋友圈的根r，然後把以r為根的這個圈子的人數加上以t為根的圈子的朋友數。這樣最後只要找f【i】 == i（這樣的i是根）的這樣的圈子的朋友數，找最大的。

代碼：

#include 
#include 

const int N = 30005;
int n, m , t, f[N], c[N];

void init () {

	for (int i = 0; i <= n; i++ ) {

		f[i] = i;
		c[i] = 1;
	}
}
	
int  getfather (int x) {

 	return	f[x] = ( f[x] == x ) ? x : getfather (f[x]);
}

int main () {

	scanf ("%d", &t);
	while (t--) {
	
		scanf ("%d%d", &n, &m);
		int x, y;
		init();
		for (int i = 0; i < m; i++) {

			scanf ("%d%d", &x, &y);
			int p = getfather(x);
			int q = getfather(y);
			if (p !=  q){
				
				c[p] += c[q];
				f[q] = p;
			}

		}
		int max = 0;
		for (int i = 1; i <= n; i++)
			if (i == f[i] && max < c[i])
				max = c[i];
		printf ("%d\n", max);	

	}
	return 0;
}