#543. SPANNING – Cây khung

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho đơn đồ thị vô hướng liên thông G(V, E) n đỉnh và m cạnh. Hãy xây dựng cây khung của G .

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên n m là số đỉnh và số cạnh của 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 cạnh nối hai đỉnh u v trong G

Dữ liệu ra:

  • Danh sách các cạnh của cây khung ( n – 1 cạnh, mỗi cạnh trên một dòng).

Ví dụ:

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

Giới hạn:

  • 1 ≤ n ≤ 10000; 0 ≤ m ≤ 500000 ≤ \frac{n(n – 1)}{2} .