Dang_Quan_10_Tin

CONSTRUCT (CSPTST 2017-2018)

Aug 3rd, 2021
624
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define task ""
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6.  
  7. const int N = 1e5 + 5;
  8. struct dsu{
  9.     int par[N];
  10.     dsu() {
  11.         memset(par, -1 , sizeof par);
  12.     }
  13.     int findpar(int v) {
  14.         return par[v] < 0 ? v : par[v] = findpar(par[v]);
  15.     }
  16.     void Merge(int v, int u) {
  17.         u = findpar(u);
  18.         v = findpar(v);
  19.         if(u == v) return;
  20.         if(par[u] < par[v]) swap(u, v);
  21.         par[v] += par[u];
  22.         par[u] = v;
  23.     }
  24. } f;
  25.  
  26. int m, n, low[N], num[N], l(0), dp[N];
  27. int id[N * 2], x[N * 2], y[N * 2];
  28. int max1[N], max2[N], dep[N];
  29. vector<pair<int, int>> adj[N];
  30. vector<int> nadj[N];
  31. bool critical[N * 2], ck[N];
  32.  
  33. void Read() {
  34.     cin >> n >> m;
  35.     for(int i = 1; i <= m; ++i) {
  36.         int u, v;
  37.         cin >> u >> v;
  38.         id[i] = i;
  39.         if(u != v) {
  40.             x[i] = u;
  41.             y[i] = v;
  42.             adj[u].emplace_back(v, i);
  43.             adj[v].emplace_back(u, i);
  44.         }
  45.     }
  46. }
  47.  
  48. void dfs(int v, int p) {
  49.     low[v] = num[v] = ++l;
  50.     for(auto i : adj[v])
  51.         if(i.first != p) {
  52.             if(num[i.first]) low[v] = min(low[v], num[i.first]);
  53.             else {
  54.                 dfs(i.first, v);
  55.                 low[v] = min(low[v], low[i.first]);
  56.                 critical[i.second] = low[i.first] > low[v];
  57.             }
  58.         }
  59. }
  60.  
  61. void dfs2(int v) {
  62.     ck[v] = 1;
  63.     max1[v] = max2[v] = dep[v];
  64.     dp[v] = 0;
  65.  
  66.     for(auto i : nadj[v])
  67.         if(!ck[i]) {
  68.             dep[i] = dep[v] + 1;
  69.             dfs2(i);
  70.             dp[v] = max(dp[v], dp[i]);
  71.             if(max1[v] < max1[i]) {
  72.                 max2[v] = max1[v];
  73.                 max1[v] = max1[i];
  74.             }
  75.             else if(max2[v] < max1[i]) max2[v] = max1[i];
  76.         }
  77.     dp[v] = max(dp[v], max1[v] + max2[v] - 2 * dep[v]);
  78. }
  79.  
  80. void Solve() {
  81.     for(int i = 1; i <= n; ++i)
  82.         if(!num[i])
  83.             dfs(i, 0);
  84.     sort(id + 1, id + m + 1, [&](const int &u, const int &v) {
  85.          return x[u] < x[v] || (x[u] == x[v] && y[u] < y[v]);
  86.     });
  87.     //cerr << "ok\n";
  88.  
  89.     for(int i = 1, j = 1; i <= m; ++i) {
  90.         while(j <= m && x[id[i]] == x[id[j]] && y[id[i]] == y[id[j]]) ++j;
  91.         if(j - i > 1)
  92.             while(i < j) critical[id[i++]] = 0;
  93.         i = j - 1;
  94.     }
  95.  
  96.     for(int i = 1; i <= m; ++i)
  97.         if(!critical[i] && x[i] && y[i])
  98.             f.Merge(x[i], y[i]);
  99.  
  100.     for(int i = 1; i <= m; ++i)
  101.         if(critical[i] && x[i] && y[i]) {
  102.             nadj[f.findpar(x[i])].emplace_back(f.findpar(y[i]));
  103.             nadj[f.findpar(y[i])].emplace_back(f.findpar(x[i]));
  104.         }
  105.  
  106.     int ans(0);
  107.  
  108.     for(int i = 1; i <= n; ++i)
  109.         if(!ck[f.findpar(i)]) {
  110.             dfs2(f.findpar(i));
  111.             ans = max(ans, dp[f.findpar(i)]);
  112.         }
  113.  
  114.     cout << ans;
  115. }
  116.  
  117. int32_t main()
  118. {
  119.     ios_base::sync_with_stdio(0);
  120.     cin.tie(0);
  121.     Read();
  122.     Solve();
  123. }
RAW Paste Data