Problem: 交作业

Problem: 交作业

Time Limit: 2 Sec Memory Limit: 128 MB

Description

又到了交作业的时间了,都要找wyf学霸抄作业,但wyf只会借作业给朋友,幸好朋友会借给朋友的朋友.但不是朋友就不会分享,问最后谁写了作业,朋友是相互的,wyf编号是1

Input

第一行n,m,学生数和m对朋友，下来m行,ai和bi是朋友

Output

谁写了作业

Sample Input

10 9
1 4
1 8
1 7
2 3
4 8
5 6
6 7
6 8
9 10

Sample Output

1 4 5 6 7 8

HINT

本题用并查集的方法，就是每输入两个数，先判断是否在同一集合内，否则合并。最后查找答案时，找出哪些数与1在同一集合内。
实际上，只需要find(1)==find(x)就可以了。

Code

/* -std=c99 -DDebug=1*/
#include<stdio.h>
int n,m,a,b;
int fa[1001];
int find(int x) {
	return x==fa[x]?x:(fa[x]=find(fa[x]));//并查集版find
}
#if Debug
int Debug_find(int x) {
	return x==fa[x]?x:find(fa[x]);//普通版find,防止换爸爸
}
#endif
void merge(int a,int b) {
	int x=find(a),y=find(b);
	if(x!=y) fa[x]=y;
	//如果没有共同祖先就连接
}
int main() {
	register int i;
	scanf("%d%d",&n,&m);
	for(i=1; i<=n; i++) fa[i]=i;
	/*
	 *初始化
	 *每个人都是自己的爸爸(总觉得怪怪的)
	 *(每个人都是根)
	 */
	for(i=1; i<=m; i++) {
		scanf("%d%d",&a,&b);
		merge(a,b);
	}
	int Henry=find(1);
#if Debug
	printf("<Debug> Henry == %d
",Henry);
	for(i=1; i<=n; i++)
		printf("<Debug> Father_of_%d == %d
",i,fa[i]);
	for(i=1; i<=n; i++)
		printf("<Debug> Root_of_%d == %d
",i,Debug_find(i));
#endif
	for(i=1; i<=n; i++)
		if(Henry==find(i))//如果ta和学霸Henry在一颗树上
			printf("%d ",i);//就输出
	return 0;
}

▲并查集与不用并查集的区别

▲并查集与不用并查集的区别