VM 10 Bài 01 - Điều kiện thời tiết

View as PDF
Submit solution
Points: 0.21 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
VM10 (Luyện Tập) - Nguồn: Ukrainian OI
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hãng hàng không OlympAirways thực hiện các chuyến bay giữa ~n~ sân bay được đánh số từ ~1~ đến ~n~. Hệ thống các chuyến bay được thiết lập sao cho giữa ~2~ sân bay bất kỳ được phục vụ bởi hãng luôn có một đường bay bao gồm một hoặc nhiều chuyến bay trực tiếp giữa hai sân bay. Mỗi chuyến bay thực hiện việc di chuyển giữa hai thành phố theo cả hai chiều.

Trung tâm điều khiển của hãng đưa ra khái niệm độ dính kết giữa cặp hai sân bay ~A~ và ~B~ được xác định như là số lượng các chuyến bay mà việc không thực hiện một trong số chúng (các chuyến bay khác vẫn thực hiện bình thường) dẫn đến không thể bay từ sân bay ~A~ đến sân bay ~B~.

Một nghiên cứu cho biết rằng, trong điều kiện thời tiết xấu, tổng độ dính kết giữa các cặp sân bay phải đạt đến một giá trị nhất định thì hệ thống đường bay mới được gọi là an toàn.

Yêu cầu: Hãy giúp trung tâm điều khiển tính tổng độ dính kết giữa mọi cặp sân bay.

Input

  • Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 100~)
  • Dòng thứ hai chứa số nguyên ~m~ (~1 \leq m \leq 5000~) - số lượng các chuyến bay
  • Mỗi dòng trong số ~m~ dòng tiếp theo chứa thông tin về một chuyến bay, bao gồm hai số nguyên dương trong khoảng từ ~1~ đến ~n~: chỉ số của hai sân bay được nối bởi chuyến bay.

Output

In ra ~1~ số nguyên duy nhất là tổng độ dính kết giữa mọi cặp sân bay (~A~, ~B~) (với ~A < B~).

Sample Input

5
5
1 2
4 2
4 5
3 2
3 1

Sample Output

10

Comments

Please read the guidelines before commenting.


  • -2
    huyjav  commented on Aug. 18, 2024, 4:14 p.m. ← edited

    skibidi


  • -3
    k116anhnguyenhatruc  commented on July 11, 2024, 8:12 a.m. ← edit 2

    .


  • -4
    khaokhatdtqg  commented on Sept. 27, 2023, 1:16 a.m.

    low[v] >= num[v] thể hiện điều gì vậy mng🥹


    • -4
      sitingfake  commented on July 19, 2024, 12:28 p.m.

      == moi dung nha ban hoac la low[v]>num[u];


    • -4
      phuctieuhoang  commented on Jan. 29, 2024, 1:43 p.m.

      tarjan nha


  • 7
    kennikai  commented on Aug. 10, 2022, 1:43 a.m.

    bạn nào tốt bụng giải thích test cho mình với, đọc mãi k hiểu, lú quá


    • 60
      PPAP_1264589  commented on Aug. 10, 2022, 2:13 a.m. ← edited

      Phát biểu lại đề bài:

      Với mỗi cặp đỉnh ~(u, v)~ trên đồ thị, tìm tập hợp ~C~ lớn nhất gồm các cạnh, mà khi bỏ đi ~1~ trong những cạnh đó, sẽ dẫn đến ~u~ không đi được đến ~v~

      -> Tính tổng số phần tử của tất cả các tập hợp đó

      Giải thích test ví dụ:

      1. các cặp đỉnh ~(5, 2), (5, 3), (5, 1)~ đều có ~|C| = 2~, cụ thể là nếu bỏ đi một trong hai cạnh trên đồ thị: ~(5, 4)~ hoặc ~(4, 2)~ đều dẫn đến ~5~ không đi được đến ~2, 3, 1~

      2. các cặp đỉnh ~(4, 2), (4, 3), (4, 1)~ đều có ~|C| = 1~ là cạnh ~(4, 2)~

      3. cặp đỉnh ~(5, 4)~ có ~|C| = 1~ là cạnh ~(5, 4)~

      các cặp đỉnh còn lại, đều không thể tìm được tập hợp ~C~ thỏa mãn

      ~-> 2+2+2+1+1+1+1 = 10~