Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

STROCONN - Thành phần liên thông mạnh (cơ bản)

Đồ thị có hướng G(V, E) được gọi là liên thông mạnh (strongly connected) nếu giữa mọi cặp đỉnh của G luôn tồn tại đường đi (định hướng).

Cho đồ thị có hướng G = (V, E), U là một tập con của V. Ta nói U là một thành phần liên thông mạnh của G nếu hạn chế của G trên tập U: GU = (U, EU) là một đồ thị liên thông mạnh. 

Bài toán: Cho đồ thị có hướng G(V, E) có n đỉnh và m cung. Hãy tìm các thành phần liên thông mạnh của G. 

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên n và m là số đỉnh và số cung của đồ thị G.
  • m dòng tiếp theo, mỗi dòng chứa một cặp số u, v cho biết một cung nối từ u tới v trong G.

Dữ liệu ra:

  • Dòng đầu ghi số nguyên dương C là số thành phần liên thông mạnh trong G.
  • C dòng tiếp theo, mỗi dòng ghi một thành phần liên thông mạnh theo khuôn dạng: Số v đầu là số đỉnh của thành phần liên thông mạnh, v số tiếp theo là danh sách các đỉnh của thành phần liên thông đó.

Hai số trên cùng một dòng được ghi cách nhau một dấu cách.

Ví dụ:

 

STROCONN

Dữ liệu vào:
6 8
1 2
2 3
2 5
3 1
3 4
4 6
5 4
6 5

Dữ liệu ra:
2
3 1 2 3
3 4 5 6

Giới hạn: 1 ≤ n  1000; 0  m  n(n – 1)/2. 


Được gửi lên bởi:noname00.pas
Ngày:2017-10-22
Thời gian chạy:0.100s-0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3
Nguồn bài:Bài tập thực hành CSL

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.