3424 . [模板題] Connected Components of Complement Graph

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

50.0% (2/4)

Tags

library-checker template

Description

You are given a simple undirected graph with $N$ vertices and $M$ edges. The $i$-th edge is $(a_ i,b_ i)$. Decompose the complement graph of $G$ into connected components.

Input Format

$N$ $M$
$a_ 0$ $b_ 0$
$a_ 1$ $b_ 1$
$\vdots$
$a_ {M-1}$ $b_ {M-1}$

Output Format

Print the number of connected components $K$ in the first line. In the next $K$ lines, print as follows. $l$ is the number of vertices of a connected component and $v_ i$ is a vertex index.
$l$ $v_ 0$ $v_ 1$ ... $v_ {l-1}$

If there are multiple solutions, you may print any of them.

Sample Input 1

4 3
1 0
2 1
1 3

Sample Output 1

2
3 0 2 3
1 1

Sample Input 2

6 11
0 1
0 2
0 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
4 5

Sample Output 2

3
3 0 3 5
2 1 4
1 2

Sample Input 3

5 10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 3

5
1 4
1 3
1 2
1 1
1 0

Hints

  • $1 \leq N \leq 5 \times 10^ {5}$
  • $0 \leq M \leq 5 \times 10^ {5}$
  • $0 \leq a_ i, b_ i < N$
  • The given graph is simple

Problem Source

library checker: connected_components_of_complement_graph

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152
16 5000 2097152 2097152
17 5000 2097152 2097152
18 5000 2097152 2097152
19 5000 2097152 2097152
20 5000 2097152 2097152
21 5000 2097152 2097152
22 5000 2097152 2097152
23 5000 2097152 2097152
24 5000 2097152 2097152
Submit
Back to Top