CSES - Graph Girth | Chu vi đồ thị

Xem PDF
Tác giả:
letangphuquy , Flower_On_Stone , SPyofgame
Dạng bài
Đ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


  • -1
    nguyen_ducminh    1:13 a.m. 16 Tháng 9, 2023

    CSES - Graph Girth | Chu vi đồ thị

    Cho một đồ thị vô hướng, nhiệm vụ của bạn là xác định chu vi của nó, tức độ dài chu trình ngắn nhất của đồ thị.

    Input

    • Dòng đầu tiên gồm hai số nguyên \(n\) (\(1 \leq n \leq 2500\)) và \(m\) (\(1 \leq m \leq 5000\)) - số lượng đỉnh và cạnh của đồ thị. Các đỉnh được đánh chỉ số \(1, 2, ..., n\).
    • \(m\) dòng tiếp theo mô tả các cạnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\) với ý nghĩa có cạnh nối giữa hai đỉnh \(a\) và \(b\).

    Đồ thị đã cho đảm bảo giữa hai đỉnh bất kì có tối đa một cạnh nối giữa chúng.

    Output

    • In ra một số nguyên - chu vi của đồ thị. Nếu đồ thị không có chu trình, in ra -1.

    Test 1

    Input 
    5 6
1 2
1 3
2 4
2 5
3 4
4 5
    Output 
    3
      • 1 bình luận nữa