UOJ Logo

NOI.AC

1S 512MB

#1293. 部落联盟

Statistics

题目描述

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

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

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

题目输入

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

接下来$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%的数据有:$1 \leq n, m \leq 100, 1 \leq u[i], v[i] \leq n$。

对于100%的数据有:$1 \leq n, m \leq 10^5, 1 \leq u[i], v[i] \leq n$。

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