Close Group

题目描述

给定一个含有 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1, 2, \dots, N$，第 $i$ 条边连接顶点 $A_i$ 与 $B_i$。 在可以删除零条或多条边的前提下，使下述条件得到满足后，求图中连通分量数量的最小可能值： Condition:
对于任意满足 1 \le a < b \le N 的顶点对 $(a, b)$，若顶点 $a$ 和 $b$ 属于同一个连通分量，则存在一条边直接连接顶点 $a$ 与 $b$。

输入格式

输入按照下述格式由标准输入给出： $N$ $M$ $A_1$ $B_1$ $\vdots$ $A_M$ $B_M$

输出格式

输出答案。

3 2
1 2
1 3

2

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

1

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

5

18 0

18

提示

输入中的所有值均为整数。 $1 \le N \le 18$ $0 \le M \le \frac{N(N - 1)}{2}$ 1 \le A_i < B_i \le N $(A_i, B_i) \neq (A_j, B_j)$ 当 $i \neq j$ 时。在不删除任何边的情况下，顶点对 $(2, 3)$ 违反了该条件。 删除其中一条边会使顶点 $2$ 与 $3$ 不连通，从而满足该条件。

标签: AtCoder|abc187F

来源

AtCoder|abc187F