← 返回题目列表

AtCoder · abc284_c

E. 计算连接的组件

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个简单的无向图 N 顶点编号 1 to N 和 M 边编号 1 to M。边缘 i 连接顶点 u_i 和顶点 v_i.
求此图中连通分量的数量。

注释

A 简单无向图 是一个简单且具有无向边的图。
图表是 简单 当且仅当它没有自环或多边时。

A 子图 图的 是由该图的一些顶点和边形成的图。
图表是 已连接 当且仅当可以通过边在每对顶点之间移动。
A 连接的组件 是一个连通子图,不属于任何更大的连通子图。

约束

  • 1 \leq N \leq 100
  • 0 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq u_i, v_i \leq N
  • 给定的图表很简单。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

输出

打印答案。


示例输入 1

5 3
1 2
1 3
4 5

示例输出 1

2

给定的图包含以下两个连接的组件:

  • 由顶点形成的子图 1, 2, 3和边缘 1, 2;
  • 由顶点形成的子图 4, 5,和边缘 3.

image


示例输入 2

5 0

示例输出 2

5

示例输入 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

示例输出 3

1