CSES - Graph Girth | Chu vi đồ thị

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
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

    • 0
      dang7rickroll    10:02 p.m. 28 Tháng 8, 2022

      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:

      • Duyệt qua tất cả các đỉnh của đồ thị;
      • Với mỗi đỉnh thì ta BFS, lưu lại khoảng cách từ đỉnh đó đến các đỉnh con của đỉnh đang xét, đánh dấu đỉnh;
      • Nếu gặp đỉnh đã duyệt thì tức là đã tìm được chu trình, đo khoảng cách của chu trình và lấy chu trình có khoảng cách nhỏ nhất.

      Độ phức tạp tổng thể của bài toán là \(\mathcal{O}(n\cdot (n +m ))\)