ĐỀ LUYỆN TẬP ĐỒ THỊ 

Bài 1. Khoảng cách từ nguồn

Cho đồ thị vô hướng gồm N đỉnh, M cạnh. Các đỉnh được đánh số từ 1 đến N. Mỗi cạnh nối hai đỉnh khác nhau và không có cạnh trùng. Cho đỉnh xuất phát S.

Với mỗi đỉnh i, hãy tìm số cạnh ít nhất trên một đường đi từ S đến i. Nếu không thể đi từ S đến i, in -1.

Dữ liệu vào (KHOANGCACH.INP):
Dòng 1 gồm N, M (1 ≤ N ≤ 2·10^5; 0 ≤ M ≤ 2·10^5).
Dòng 2 gồm S.
M dòng tiếp theo, mỗi dòng gồm u, v mô tả một cạnh vô hướng.

Kết quả (KHOANGCACH.OUT):
In N số nguyên trên một dòng, số thứ i là khoảng cách ngắn nhất từ S đến i, hoặc -1 nếu không tới được.

Ví dụ:

Input

5 3

1

1 2

2 3

4 5

Output

0 1 2 -1 -1

Giới hạn: Đồ thị không nhất thiết liên thông.

Bài 2. Đếm miền kết nối

Một mạng gồm N máy tính và M đường nối hai chiều. Hai máy thuộc cùng một miền kết nối nếu có thể đi từ máy này đến máy kia qua một số đường nối.

Hãy đếm số miền kết nối của mạng.

Dữ liệu vào (MIENKETNOI.INP):
Dòng 1 gồm N, M (1 ≤ N ≤ 2·10^5; 0 ≤ M ≤ 2·10^5).
M dòng tiếp theo, mỗi dòng gồm u, v (1 ≤ u, v ≤ N; u ≠ v), mô tả một đường nối. Không có đường nối trùng.

Kết quả (MIENKETNOI.OUT):
In ra một số nguyên là số miền kết nối.

Ví dụ:

Input

6 3

1 2

2 3

4 5

Output

3

Bài 3. Đường đi ngắn nhất

Cho đồ thị vô hướng không trọng số gồm N đỉnh và M cạnh, đánh số đỉnh từ 1 đến N. Cho hai đỉnh S và T.

Hãy tìm một đường đi ngắn nhất từ S đến T. Nếu không tồn tại đường đi, in -1.

Dữ liệu vào (DUONGDI.INP):
Dòng 1 gồm N, M (1 ≤ N ≤ 2·10^5; 0 ≤ M ≤ 2·10^5).
Dòng 2 gồm S, T.
M dòng tiếp theo, mỗi dòng gồm u, v mô tả một cạnh vô hướng. Không có cạnh trùng và không có khuyên.

Kết quả (DUONGDI.OUT):
Nếu không có đường đi, in duy nhất -1.
Ngược lại, in dòng 1 số cạnh của đường đi d. In dòng 2 gồm d+1 đỉnh theo thứ tự từ S đến T. Đường đi phải có đúng d cạnh và d là nhỏ nhất có thể. Nếu có nhiều đường đi ngắn nhất, chấp nhận bất kỳ đường đi nào hợp lệ.

Ví dụ:

Input

5 5

1 5

1 2

2 5

1 3

3 4

4 5

Output

2

1 2 5

Lưu ý: Ví dụ chỉ minh họa một kết quả hợp lệ; đường đi 1-3-4-5 không ngắn nhất.

Bài 4. Tìm một chu trình

Cho đồ thị vô hướng đơn gồm N đỉnh và M cạnh. Hãy tìm một chu trình đơn trong đồ thị nếu có.

Chu trình đơn là dãy đỉnh v1, v2, ..., vk (k ≥ 3), các đỉnh v1,...,vk đôi một khác nhau, và tồn tại các cạnh (v1,v2), (v2,v3), ..., (v(k-1),vk), (vk,v1).

Dữ liệu vào (CHUTRINH.INP):
Dòng 1 gồm N, M (1 ≤ N ≤ 2·10^5; 0 ≤ M ≤ 2·10^5).
M dòng tiếp theo, mỗi dòng gồm u, v mô tả một cạnh vô hướng. Không có cạnh trùng và không có khuyên.

Kết quả (CHUTRINH.OUT):
Nếu đồ thị không có chu trình, in -1.
Nếu có chu trình, in dòng 1 số k là số đỉnh của chu trình (k ≥ 3), dòng 2 in k đỉnh theo thứ tự trên chu trình. Đỉnh cuối phải nối được với đỉnh đầu bằng một cạnh. Có thể in bất kỳ chu trình đơn hợp lệ nào.

Ví dụ:

Input

4 4

1 2

2 3

3 1

3 4

Output

3

1 2 3

Bài 5. Nối mạng với chi phí nhỏ nhất

Có N địa điểm và M tuyến cáp có thể lắp đặt. Tuyến cáp thứ i nối hai địa điểm u_i, v_i và có chi phí w_i. Hãy chọn các tuyến cáp sao cho mọi địa điểm đều kết nối được với nhau và tổng chi phí là nhỏ nhất.

Dữ liệu vào (CAYKHUNG.INP):
Dòng 1 gồm N, M (1 ≤ N ≤ 2·10^5; 0 ≤ M ≤ 3·10^5).
M dòng tiếp theo gồm u, v, w (1 ≤ u, v ≤ N; u ≠ v; 1 ≤ w ≤ 10^9), mô tả một tuyến cáp vô hướng. Không có tuyến cáp trùng giữa cùng một cặp đỉnh.

Kết quả (CAYKHUNG.OUT):
In tổng chi phí nhỏ nhất để kết nối tất cả các địa điểm. Nếu không thể kết nối tất cả các địa điểm, in -1.

Ví dụ:

Input

4 5

1 2 3

2 3 2

3 4 4

1 4 10

1 3 5

Output

9