Tìm vùng liên thông có nhiều đỉnh nhất.

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Vùng liên thông trong đồ thị là tập hợp các đỉnh mà từ một đỉnh bất kỳ có đường đi trực tiếp hoặc gián tiếp đến các đỉnh khác trong tập hợp đó. Cho đồ thị vô hướng có ~N~ đỉnh, ~M~ cạnh. Hãy liệt kê vùng liên thông có nhiều đỉnh nhất trong đồ thị. Mỗi số cách nhau một dấu cách, nếu có nhiều vùng liên thông có cùng số lượng đỉnh nhiều nhất thì đưa ra vùng liên thông có thứ tự từ điển nhỏ nhất.

Dữ liệu:

  • Dòng 1: Ghi số nguyên ~N~ và ~M (M, N ≤ 3000)~.
  • ~M~ dòng tiếp theo, mỗi dòng ghi số nguyên dương ~u~ và ~v~ thể hiện có đường đi giữa hai đỉnh ~u~ và ~v (u, v ≤ N)~.

Kết quả:

  • Dòng 1: Ghi số lượng đỉnh trong vùng liên thông tìm được.
  • Dòng 2: Các đỉnh trong vùng liên thông tìm được, được sắp xếp thành dãy tăng. Mỗi số cách nhau một dấu cách.
Ví dụ:
INPUT
12 7
1 2
2 5
2 6
6 10
3 4
9 11
9 12
OUTPUT
5
1 2 5 6 10

Comments

Please read the guidelines before commenting.


There are no comments at the moment.