Advertisement
Dang_Quan_10_Tin

MỘT ĐƯỜNG ĐI

Aug 15th, 2022 (edited)
636
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. constexpr int N = 1e6 + 5;
  7. constexpr int mod = 123456789;
  8.  
  9. int n, m;
  10. vector<pair<int, int>> adj[N]; // Trong danh sách kề, anh lưu hai giá trị là {đỉnh, chỉ số cạnh (thứ tự nhập vào của cạnh trong input)}
  11.  
  12. int low[N], num[N], l; // Phục vụ cho quá trình dfs tìm cầu
  13.  
  14. bitset<N> vis; // Mảng đánh dấu đã duyệt qua bởi dfs chưa
  15. bitset<N * 5> Critical; // Mảng đánh dấu cạnh
  16.  
  17. void Read()
  18. {
  19.     cin >> n >> m;
  20.  
  21.     for (int i = 1; i <= m; ++i)
  22.     {
  23.         int u, v;
  24.         cin >> u >> v;
  25.  
  26.         adj[u].emplace_back(v, i);
  27.         adj[v].emplace_back(u, i);
  28.     }
  29. }
  30.  
  31.  
  32. // Quá trình thực hiện thuật toán Tarjan
  33. void dfs(int v, int p = -1)
  34. // Tham số của hàm dfs gồm có 2 giá trị là v - đỉnh hiện tại và p-cạnh vừa đi qua để đến v
  35. // Nhiều nơi (Hầu hết trên mạng) hướng dẫn code tarjan lưu p là cha của v nhưng cách làm này không đúng với đa đồ thị
  36. // Trên thực tế, ta chỉ cần không đi lại cạnh vừa đi qua là được, đây chính là lí dó anh lưu lại chỉ số cạnh trong danh sách kề
  37. {
  38.     low[v] = num[v] = ++l;
  39.  
  40.     for (auto i : adj[v])
  41.         if (i.second != p)
  42.         // Nếu cạnh này không phải là cạnh vừa được duyệt qua
  43.         {
  44.             if (!num[i.first]) // Nếu đỉnh i.first chưa được duyệt qua
  45.             {
  46.                 dfs(i.first, i.second);
  47.                 low[v] = min(low[v], low[i.first]);
  48.  
  49.                 if (low[i.first] > num[v])
  50.                 // Theo VNOI Wiki, low[i.first] == num[i.first], nhưng hai điều kiện này là tương đương nhau
  51.                     Critical[i.second] = 1;
  52.             }
  53.             else {
  54.                 low[v] = min(low[v], num[i.first]);
  55.                 // Các em cần chú ý đoạn này, vì là đa đồ thị nên rất có thể cạnh này nối đến một con cháu của nó 
  56.                 // Trong bài toán tìm cầu khớp, điều này không ảnh hưởng nhiều; song trong nhiều bài toán khác có thêm điều kiện, ta cần chú ý về điều kiện này có làm ảnh hưởng đến thuật toán ta thiết kế hay không     
  57.             }
  58.         }
  59. }
  60.  
  61. // Liệt kê thành phần liên thông sử dụng BFS
  62. ll BFS(int x)
  63. {
  64.     int cnt(0); // Duy trì số lượng đỉnh của thành phần liên thông
  65.     ll sum(0); // Duy trì tổng chỉ số của thành phần liên thông
  66.  
  67.     queue<int> q;
  68.  
  69.     q.emplace(x);
  70.     vis[x] = 1;
  71.  
  72.     while (!q.empty())
  73.     {
  74.         int c = q.front();
  75.         q.pop();
  76.  
  77.         ++cnt;
  78.         sum += c;
  79.  
  80.         for (auto i : adj[c])
  81.             if (Critical[i.second] && !vis[i.first]) /// Anh chỉ đi qua cầu
  82.             {
  83.                 q.emplace(i.first);
  84.                 vis[i.first] = 1;
  85.             }
  86.     }
  87.  
  88.     return sum * cnt; // Số đỉnh * Tổng chỉ số
  89. }
  90.  
  91. void Solve()
  92. {
  93.     for (int i = 1; i <= n; ++i)
  94.         if (!num[i])
  95.             dfs(i);
  96.  
  97.     ll ans(0);
  98.  
  99.     for (int i = 1; i <= n; ++i)
  100.         if (!vis[i])
  101.             (ans += BFS(i)) %= mod;
  102.  
  103.     cout << ans;
  104. }
  105.  
  106. int32_t main()
  107. {
  108.     ios::sync_with_stdio(0);
  109.     cin.tie(0);
  110.     cout.tie(0);
  111.     Read();
  112.     Solve();
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement