AT_abc187_f [ABC187F] Close Group

题目描述

给定一个有 $N$ 个顶点 $M$ 条边的简单无向图。该图的顶点编号为 $1, 2, \dots, N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

请你求出，在满足以下条件的前提下，通过去除 $0$ 条或多条边后，图的连通分量个数可能的最小值。

条件
对于任意满足 $1 \leq a < b \leq N$ 的顶点对 $(a, b)$，如果顶点 $a$ 和顶点 $b$ 属于同一个连通分量，则顶点 $a$ 和顶点 $b$ 之间必须直接有一条边相连。

输入格式

输入以如下格式从标准输入中给出。

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 2
1 2
1 3

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

1

输入输出样例 #3

输入 #3

10 11
9 10
2 10
8 9
3 4
5 8
1 8
5 6
2 5
3 6
6 9
1 9

输出 #3

5

输入输出样例 #4

输入 #4

18 0

输出 #4

18

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 18$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i < B_i \leq N$
• 如果 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$

样例解释 1

如果不去除任何边，则 $(2, 3)$ 这对顶点不满足条件。去除其中一条边后，顶点 $2$ 和顶点 $3$ 不再连通，条件得以满足。

由 ChatGPT 4.1 翻译