Hướng dẫn cho Đếm tam giác trong đồ thị
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Gọi \(d[u]\) là số cạnh đi qua đỉnh \(u\). Ta sắp các đỉnh theo cặp \((d[u], u)\): đỉnh có bậc nhỏ hơn đứng trước; nếu bậc bằng nhau, đỉnh có số nhỏ hơn đứng trước.
Với mỗi cạnh, hướng cạnh từ đỉnh đứng trước sang đỉnh đứng sau. Gọi adj[u] là danh sách các đỉnh mà cạnh từ \(u\) hướng tới. Với mỗi đỉnh \(u\):
- Đánh dấu tất cả các đỉnh trong
adj[u]. - Với mỗi \(v\) trong
adj[u], duyệt từng \(w\) trongadj[v]. Nếu \(w\) đã được đánh dấu, ta tìm được một tam giác.
Có thể dùng mark[w] = u để đánh dấu đỉnh \(w\) trong lượt của \(u\), nên không cần xóa dấu sau mỗi lượt. Mảng được khởi tạo bằng \(0\), còn các đỉnh được đánh số từ \(1\).
Vì sao mỗi tam giác được đếm đúng một lần?
Với một tam giác, gọi ba đỉnh theo thứ tự đã chọn là \(a, b, c\). Ba cạnh sẽ có hướng \(a \to b\), \(a \to c\) và \(b \to c\).
Khi xét \(a\), ta đánh dấu \(c\), rồi tìm thấy \(c\) trong adj[b]. Các lượt của \(b\) và \(c\) không thể tìm lại đủ ba cạnh này. Vì vậy mỗi tam giác được đếm đúng một lần. Ngược lại, mỗi lần tăng đáp án đều có đủ ba cạnh của một tam giác.
Độ phức tạp
Mỗi đỉnh có \(O(\sqrt m)\) cạnh hướng ra. Nếu \(d[u] \le \sqrt{2m}\), điều này đúng vì số cạnh hướng ra không vượt quá \(d[u]\). Nếu \(d[u] > \sqrt{2m}\), mọi đỉnh mà \(u\) hướng tới đều có bậc ít nhất \(d[u]\). Do tổng bậc là \(2m\), có không quá \(2m/d[u] < \sqrt{2m}\) đỉnh như vậy.
Mỗi cạnh \(u \to v\) khiến ta duyệt adj[v] một lần. Tổng thời gian là \(O(n + m\sqrt m)\), bộ nhớ là \(O(n + m)\). Khi \(m = 0\), chương trình chỉ cần khởi tạo và duyệt các đỉnh, mất \(O(n)\) thời gian.
Chỉ hướng cạnh theo số hiệu đỉnh có thể khiến chương trình duyệt quá nhiều lần trên đồ thị hình sao. Việc so sánh bậc trước, rồi mới so sánh số hiệu đỉnh, giúp giữ giới hạn trên.
Đáp án không cần lấy dư. Trong C++, dùng long long để lưu đáp án; Python dùng số nguyên thông thường.
Bình luận