问题 1017. -- 找出民族

1017: 找出民族

时间限制: 1000 Sec  内存限制: 0 MB
提交: 121  解决: 78
[提交][状态][讨论版]

题目描述

世界上有许多不同的民族,现在有一个比较感兴趣的话题:在你的周围人群中找出不同民族的种类数。假设你的周围有n个人(0 < n < 10000),若直接问每一个人什么民族不大合适,许多人还不太愿意说出自己的民族。有一种方法可以回避这个问题:询问其中的m对人,问他们是否属于同一个民族。通过这个数据,你可能不知道每个人具体的民族,但是你可以知道大概有多少个民族,假设每个人只属于一个民族。

输入

输入多组测试数据,每组数据的开头有两个数:n和m,占一行,人的编号从1开始到n,接下来有m行,每行有两个数i和j,代表编号为i和j的两个人同属于一个民族。每行两个数之间有一个空格,当输入n=0、m=0时,表示整个输入提前截止。

输出

  每组输出占一行,仅有一个数即不同的民族数。

样例输入

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

样例输出

7
1

提示

来源

[提交][状态]