CSES - Graph Girth | Chu vi đồ thị
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho trước một đồ thị vô hướng, bạn cần phải xác định chu vi của nó, tức là độ dài của chu trình ngắn nhất có trong đồ thị.
Input
- Dòng đầu chứa hai số nguyên \(n,m\) là số lượng đỉnh và cạnh. Các đỉnh được đánh số \(1,2,\dots,n\)
- Sau đó là \(m\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh nối giữa hai đỉnh \(a\) và \(b\).
- Dữ liệu đảm bảo đồ thị đã cho là đơn đồ thị (tối đa một cạnh nối giữa mỗi cặp đỉnh).
Output
- Một số nguyên duy nhất là chu vi của đồ thị. Nếu không có chu trình, in ra \(-1\).
Constraints
- \(1 \leq n \leq 2500\)
- \(1 \leq m \leq 5000\)
Example
Sample Input:
5 6
1 2
1 3
2 4
2 5
3 4
4 5
Sample Output:
3
Bình luận
Mình xin góp ý lời giải bài toán này như sau:
Đây là một bài BFS cơ bản, ta có thể làm như sau:
Độ phức tạp tổng thể của bài toán là \(\mathcal{O}(n\cdot (n +m ))\)
1 bình luận nữa