UVA - 10608-Friends(并查集）

题目:UVA - 10608-Friends

题目大意：给定n个人，和m个关系，m个关系代表谁和谁认识之类的，求这样的关系中，朋友圈人数最多的人数。

解题思路：这题用并查集来判断这两个人是否属于同一个朋友圈，刚开始每个人自己形成一个朋友圈，所以朋友圈人数为1，然后每碰到一个关系就判断这两个人是否属于同一个朋友圈，如果不是，就把其中一个的f【t】（t为这个圈子的根）改为另一个朋友圈的根r，然后把以r为根的这个圈子的人数加上以t为根的圈子的朋友数。这样最后只要找f【i】 == i（这样的i是根）的这样的圈子的朋友数，找最大的。

代码：

#include <stdio.h>
#include <string.h>

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;
}

UVA - 10608-Friends(并查集）,布布扣,bubuko.com

UVA - 10608-Friends(并查集）

原文：http://blog.csdn.net/u012997373/article/details/23614825