#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

并查集