#P1079. [啊哈算法]擒贼先擒王(并查集)
[啊哈算法]擒贼先擒王(并查集)
Description
警察想查清楚有几个犯罪团伙,搜集到了一些线索:
现在有10个强盗;
1号强盗与2号强盗是同伙;
3号强盗与4号强盗是同伙;
5号强盗与2号强盗是同伙;
4号强盗与6号强盗是同伙;
2号强盗与6号强盗是同伙;
8号强盗与7号强盗是同伙;
9号强盗与7号强盗是同伙;
1号强盗与6号强盗是同伙;
2号强盗与4号强盗是同伙;
强盗同伙的同伙也是同伙,请问一共有多少个独立的犯罪团伙?
Input Format
第一行n,m,分别表示强盗人数,和线索条数,接下来m行有两个数a,b,表示a和b是同伙。
Output Format
输出一个整数,表示犯罪团伙的数量
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
3
Source
并查集