UOJ Logo

NOI.AC

1S 512MB

#1293. 部落联盟

Statistics

题目描述

在二次元的世界里,有n个部落,部落用1n表示。有些部落之间通过无向的道路连接,如果两个部落可以可以通过道路互达,那么这两个部落就属于同一个联盟。例如1和2之间有一条无向的道路,2和3之间有一条无向的道路,那么1,2,3都是同一个联盟的。

给出这些部落之间的道路连接关系,判断这些部落一共形成了多少个联盟。

如果一个部落不和任何其他部落相连,那么这个部落单独形成一个联盟。两个部落之间,可能有多条无向的道路。

题目输入

第一行两个数字nm,分别表示部落的个数和道路的个数。

接下来m行,每行包含两个数字u[i]v[i],表示u[i]v[i]之间有一条无向的道路。

题目输出

输出联盟的个数。

样例输入1

5 4

1 2

2 3

3 4

4 5

样例输出1

1

样例输入2

5 3

1 2

2 1

3 4

样例输出2

3

范围说明

对于50%的数据有:1n,m100,1u[i],v[i]n

对于100%的数据有:1n,m105,1u[i],v[i]n

可能存在u[i]=v[i]