P15439 [蓝桥杯 2025 国 Python B] 连通块

题目描述

给定一个 $n$ 个点的无向完全图,从中删去 $m$ 条边,问图中有多少个连通块。 输出连通块的数量,并输出每个连通块的具体情况。

输入格式

输入的第一行包含两个正整数 $n, m$,用一个空格分隔,分别表示点数和边数。 接下来 $m$ 行,每行包含两个正整数 $u_i, v_i$,用一个空格分隔,表示删除 $u_i$ 和 $v_i$ 之间的边。保证同一条边不会被删除两次。

输出格式

输出的第一行包含一个整数 $x$,表示连通块的数量。 接下来 $x$ 行,每行包含一个连通块的描述。其中第一个数 $y$ 表示该连通块的点数,接下来 $y$ 个数,依次表示其中每个点的编号,相邻整数之间使用一个空格分隔。连通块按其中最小结点的升序输出;每个连通块内的点按升序排列。

说明/提示

### 评测用例规模与约定 对于 $40\%$ 的评测用例,$n \le 1000$; 对于所有评测用例,$1 \le n, m \le 2 \times 10^5$,$m \le \dfrac{n(n-1)}{2}$,$u_i, v_i$,$1 \le u_i, v_i \le n$。