Score : $300$ points

问题描述

你得到一个简单的无向图，其中包含 $N$ 个顶点，编号从 $1$ 到 $N$，以及 $M$ 条边，编号从 $1$ 到 $M$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

请找出此图中连通分量的数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a simple undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

• $1 \leq N \leq 100$
• $0 \leq M \leq \frac{N(N - 1)}{2}$
• $1 \leq u_i, v_i \leq N$
• The given graph is simple.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

Output

Print the answer.

Sample Input 1

5 3
1 2
1 3
4 5

Sample Output 1

2

The given graph contains the following two connected components:

• a subgraph formed from vertices $1$, $2$, $3$, and edges $1$, $2$;
• a subgraph formed from vertices $4$, $5$, and edge $3$.

Sample Input 2

5 0

Sample Output 2

5

Sample Input 3

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

Sample Output 3

1

update @ 2024/3/10 11:53:42