Phản công

Điểm: 7,00 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một đồ thị vô hướng đơn $G$ trên $N$ đỉnh được mô tả bởi danh sách $M$ cạnh. Xét đồ thị bù $\overset{―}{G}$ của $G$ : $\overset{―}{G}$ có cùng tập đỉnh, và hai đỉnh phân biệt $u, v$ kề nhau trong $\overset{―}{G}$ khi và chỉ khi $u, v$ không kề nhau trong $G$ .

Hãy tìm các thành phần liên thông của $\overset{―}{G}$ — tức là phân hoạch tập ${1, 2, \dots, N}$ thành các nhóm sao cho hai đỉnh thuộc cùng một nhóm khi và chỉ khi tồn tại đường đi giữa chúng trong $\overset{―}{G}$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$ — số đỉnh và số cạnh của $G$ .

$M$ dòng sau, dòng thứ $i$ chứa hai số nguyên $a_{i}, b_{i}$ ( $a_{i} \neq b_{i}$ ) — mô tả cạnh thứ $i$ trong $G$ . Không có cặp cạnh nào trùng lặp.

Dữ liệu ra

Dòng đầu in một số nguyên $k$ — số thành phần liên thông của $\overset{―}{G}$ .

$k$ dòng tiếp theo, mỗi dòng mô tả một thành phần: số đầu là $t_{i}$ (số đỉnh trong thành phần), tiếp theo là $t_{i}$ chỉ số đỉnh thuộc thành phần đó, cách nhau bởi dấu cách.

Thứ tự các thành phần và thứ tự các đỉnh trong mỗi thành phần không quan trọng. Tổng $\sum t_{i}$ phải bằng $N$ .

Ràng buộc

$1 \leq N \leq 5 \cdot 10^{5}$
$0 \leq M \leq 10^{6}$
$1 \leq a_{i}, b_{i} \leq N$ , $a_{i} \neq b_{i}$

Ví dụ

Input	Output	Giải thích
4 4 1 2 1 3 4 2 4 3	2 2 1 4 2 2 3	$G$ có các cạnh ${1 - 2, 1 - 3, 4 - 2, 4 - 3}$ . Trong $\overset{―}{G}$ chỉ có hai cạnh $1 - 4$ và $2 - 3$ , cho hai thành phần ${1, 4}$ và ${2, 3}$ .
3 1 1 2	1 3 1 3 2	Trong $\overset{―}{G}$ , các cạnh là $1 - 3$ và $2 - 3$ ; cả ba đỉnh nối liền qua đỉnh $3$ .
3 0	1 3 1 2 3	$G$ không có cạnh nên $\overset{―}{G}$ là đồ thị đầy đủ $K_{3}$ — tất cả đỉnh thuộc một thành phần.

Bình luận

Không có bình luận tại thời điểm này.