fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int INF = 1e9;
  9. const ll LINF = 1e18;
  10.  
  11. const int N = 1e2 + 5;
  12.  
  13. // Gọi f(u, v) là độ kết dính của hai đỉnh u, v
  14. // Ta có f(u, v) = số cạnh xuất hiện trên mọi đường đi từ u đến v
  15. // Gọi những cạnh đấy là e, ban đầu ta có u, v chung một thành phần liên thông (do u, v có thể đi đến được nhau)
  16. // Sau khi bỏ e ra khỏi đồ thị thì u, v thuộc hai thành phần liên thông khác nhau
  17. // => e là cạnh cầu
  18. // Đến đây thay vì đi tính f(u, v) với mọi (u, v)
  19. // thì với mỗi e ta sẽ đi tính g(e) = số cặp (u, v) mà sau khi bỏ e đi thì u, v không thể đi đến được nhau nữa
  20. // Giả sử e = (a, b) với a là nút cha của b trên cây dfs
  21. // Gọi sz[b] = Số đỉnh có trong cây con gốc b trên cây dfs
  22. // Ban đầu đồ thị liên thông, khi bỏ e đi thì đồ thị sẽ bị tách thành 2 thành phần liên thông
  23. // Trong đó có một thành phần liên thông có kích thước là sz[b], thành phần liên thông còn lại sẽ có kích thước là n - sz[b]
  24. // => g(e) = sz[b] * (n - sz[b])
  25.  
  26. int n, m;
  27. vector<int> adj[N];
  28.  
  29. int tin[N], low[N], timer;
  30. int sz[N]; // sz[u] = Số đỉnh có trong cây con gốc u trên cây dfs
  31.  
  32. void dfs(int u, int p) {
  33. tin[u] = low[u] = timer++;
  34. sz[u] = 1;
  35.  
  36. for (int v : adj[u]) {
  37. if (v == p) continue;
  38. if (!tin[v]) {
  39. dfs(v, u);
  40. low[u] = min(low[u], low[v]);
  41. sz[u] += sz[v];
  42. }
  43. else {
  44. low[u] = min(low[u], tin[v]);
  45. }
  46. }
  47. }
  48.  
  49.  
  50. int main() {
  51. ios::sync_with_stdio(false);
  52. cin.tie(nullptr);
  53. cin >> n >> m;
  54.  
  55. for (int i = 0; i < m; i++) {
  56. int u, v;
  57. cin >> u >> v;
  58. adj[u].push_back(v);
  59. adj[v].push_back(u);
  60. }
  61.  
  62. timer = 0;
  63. dfs(1, -1);
  64.  
  65. // Với một cạnh (u, v) bất kì sao cho u là cha của v trên cây dfs
  66. // Ngoài điều kiện low[v] > tin[u] để xác định (u, v) có phải là cạnh cầu hay không
  67. // ta còn có thể sử dụng điều kiện low[v] == tin[v] (điều kiện này hay ở chỗ ta không cần quan tâm đến nút cha của v)
  68. int ans = 0;
  69. for (int v = 1; v <= n; v++) {
  70. if (low[v] == tin[v]) {
  71. ans += sz[v] * (n - sz[v]);
  72. }
  73. }
  74.  
  75. cout << ans << '\n';
  76. }
Success #stdin #stdout 0.01s 5284KB
stdin
5
5
1 2
4 2
4 5
3 2
3 1
stdout
10