首页 > 剑指offer > 小米2013年校园招聘笔试题-简单并查集
2013
11-14

小米2013年校园招聘笔试题-简单并查集

题目描述:

假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友…),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。
假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。

输入:

输入包含多个测试用例,每个测试用例的第一行包含两个正整数 n、m,1=<n,m<=100000。接下来有m行,每行分别输入两个人的编号f,t(1=<f,t<=n),表示f和t是好友。 当n为0时,输入结束,该用例不被处理。

输出:

对应每个测试用例,输出在这n个人里一共有多少个朋友圈。

样例输入:
5 3
1 2
2 3
4 5
3 3
1 2
1 3
2 3
0
样例输出:
2
1
解题思路:这里初始为-1。 可以直接用 f[] 数组记录人数,只不过是负的。节省空间.
#include <stdio.h>
int n, m, f[100001],i;

int findSet(int x) {
	int t = x;
	while (f[x] > 0)
		x = f[x];
	while (t != x) { //路径压缩
		int q = f[t];
		f[t] = x;
		t = q;
	}
	return x;
}

void unionSet(int x, int y) {
	int fx = findSet(x);
	int fy = findSet(y);
	if (fx != fy) {
		n--;
		int tmp = f[fx] + f[fy];//两个集合个数之和
		if (f[fx] < f[fy]) {  //大集合 吞并小集合.
			f[fy] = fx;
			f[fx] = tmp;
		} else {
			f[fx] = fy;
			f[fy] = tmp;
		}
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	int a,b;
	while(scanf("%d",&n), n) {
		scanf("%d", &m);
		for( i=1; i<=n; i++)
		f[i] = -1;
		for(i=0; i<m; i++) {
			scanf("%d %d", &a,&b);
			unionSet(a,b);
		}
		printf("%d\n", n);
	}
	return 0;
}

 

 

 


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢