DeMen100ns và thành phố

Xem dạng PDF
Gửi bài giải
Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

DeMen100ns đang có một mạng lưới giao thông với ~n~ thành phố và ~m~ con đường hai chiều. Anh ấy được giao việc phải chọn ra ~3~ thành phố phân biệt ~(i, j, k)~ sao cho:

  • Tồn tại các con đường nối ~(i - j)~, ~(j - k)~ và ~(k - i)~.

Vì không biết phải chọn ra các thành phố nào, DeMen100ns muốn biết số cách anh ấy có thể chọn ra cặp ~3~ thành phố thỏa mãn điều kiện trên. Hãy giúp DeMen100ns đếm xem có bao nhiêu cách anh ấy có thể chọn.

Dữ liệu đảm bảo chỉ tồn tại nhiều nhất một con đường nối giữa hai thành phố.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(2 \le n \le 10^5, 1 \le m \le 2 * 10^5)~.

~m~ dòng tiếp theo dòng thứ ~i~ chứa hai số nguyên dương ~u~, ~v~ ~(1 \le u, v \le n, u \ne v)~ — có một con đường nối giữa thành phố ~u~ và thành phố ~v~.

Output

In ra một số duy nhất là kết quả của bài toán.

Sample Input 1

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 1

4

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 5
    YougiTuber  đã bình luận lúc 30, Tháng 6, 2025, 8:58

    Spoil ⚠️

    Mình có ~2~ cách như sau:

    Cách ~1~(Chia căn)

    Chia các đỉnh trong đồ thị thành ~2~ loại:

    Heavy : Các đỉnh có nhiều hơn ~\sqrt(n)~ đỉnh kề

    Light : Các đỉnh còn lại.

    Suy ra có không quá ~\sqrt(n)~ đỉnh Heavy

    Gọi bộ ba cần tìm là ~u, v, w~ thoả mãn ~u < v < w~, có ~4~ trường hợp sau:

    Heavy x Heavy x Heavy

    Heavy x Heavy x Light

    Light x Light x Heavy

    Light x Light x Light

    Cách tính

    Heavy x Heavy x w

    Duyệt các cặp Heavy với nhau, sau đó sử dụng ~2~ con trỏ để kiểm tra phần đỉnh ~w~ chung. Nếu đỉnh ~w~ là Heavy, cần kiểm tra ~u < v < w~, còn nếu ~w~ là Light thì đếm sẽ không trùng, chỉ cần cộng vào kết quả.

    Độ phức tạp là O(~m \cdot sqrt(n)~)

    Light x Light x w

    Duyệt các cạnh ~u, v~ trong ~m~ cạnh, nếu cả ~u~ và ~v~ là Light, thì dùng ~2~ con trỏ tương tự như phía trên, nếu ~w~ là Light thì cần kiểm tra thêm ~u < v < w~.

    Độ phức tạp là O(~m \cdot sqrt(n)~).

    Cách ~2~ (Duyệt)

    Cần đếm số bộ ba ~u, v, w~ sao cho ~u < v < w~.

    Để đếm không trùng thì ta chỉ lấy cạnh giữa ~u < v~

    Ý tưởng, duyệt ~u~, sau đó duyệt ~v~ kề ~u~, lúc này ta duy trì một mảng đánh dấu những đỉnh ~w~ thoả mãn ~v < w~ kề ~u~, và duyệt lại các đỉnh kề ~v~, nếu đỉnh đó được đánh dấu, thì ta tìm được bộ ba mới.

    Vì tổng số cạnh không quá ~m~, nên độ phức tạp của việc duyệt các đỉnh kề ~u~, ~v~ không vượt quá bậc của ~u + v~, và độ phức tạp tổng sẽ là O(~m~) ở đoạn duyệt cạnh.

    Code

    Nhập cạnh: g[u].push_back(v) ///(u < v)
for (int u=1; u<=n; u++) {
      sort(g[u].begin(), g[u].end());
      for (int v:g[u]) d[v] = 1;
      for (int v:g[u]) {
          d[v] = 0;
          for (int w:g[v]) if (d[w]) ans++;
      }
 }

    Độ phức tạp O(~m + n.log(n)~)


  • -1
    RussVN123  đã bình luận lúc 30, Tháng 6, 2025, 4:25

    wtf bài này trâu cũng AC !?


  • -25
    Loc2008  đã bình luận lúc 27, Tháng 12, 2023, 8:23

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.