fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define endl '\n'
  5. #define pi pair<int,int>
  6. #define adjs(name, type, size) vector<vector<type>>name(size)
  7. #define adjpass(name, type) vector<vector<type>>&name
  8. #define killua ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
  9. int cases = 1;
  10. int timer = 1;
  11. set<pi > bridges;
  12.  
  13. void dfsSCC(int node, int dad, vector<int> &dfn, vector<int> &lowlink, adjpass(v, int)) {
  14.     dfn[node] = lowlink[node] = timer++;
  15.     for (auto i: v[node]) {
  16.         if (i == dad)
  17.             continue;
  18.         if (dfn[i] == -1) { //not vis
  19.             dfsSCC(i, node, dfn, lowlink, v);
  20.             lowlink[node] = min(lowlink[node], lowlink[i]);
  21.             if (lowlink[i] > dfn[node]) {
  22.                 bridges.insert({min(node, i), max(node, i)});
  23.             }
  24.         } else {
  25.             lowlink[node] = min(lowlink[node], dfn[i]);
  26.         }
  27.     }
  28. }
  29.  
  30. void dfs(int node, vector<set<int >> &v, vector<int> &vis, int &last, int &mx, int cur) {
  31.     vis[node] = 1;
  32.     if (cur > mx) {
  33.         mx = cur;
  34.         last = node;
  35.     } else if (cur == mx) {
  36.         last = min(last, node);
  37.     }
  38.     for (auto i: v[node]) {
  39.         if (!vis[i]) {
  40.             dfs(i, v, vis, last, mx, cur + 1);
  41.         }
  42.     }
  43. }
  44.  
  45. class DSU {
  46. private:
  47.     vector<int> rank, par, size;
  48. public:
  49.     DSU(int n = 0) {
  50.         rank.resize(n + 1);
  51.         par.resize(n + 1);
  52.         size.resize(n + 1, 1);
  53.         for (int i = 0; i <= n; i++)
  54.             par[i] = i;
  55.     }
  56.  
  57.     int findUpar(int node) {
  58.         if (node == par[node])
  59.             return node;
  60.         return par[node] = findUpar(par[node]);//path comp
  61.     }
  62.  
  63.     void unionbyRank(int u, int v) {
  64.         int UparU = findUpar(u);
  65.         int UparV = findUpar(v);
  66.         if (UparU == UparV)
  67.             return;
  68.         if (rank[UparU] < rank[UparV]) {
  69.             par[UparU] = UparV;
  70.         } else {
  71.             par[UparV] = UparU;
  72.             rank[UparU] += (rank[UparU] == rank[UparV]);
  73.         }
  74.     }
  75.  
  76.     void unionbySize(int u, int v) {
  77.         int UparU = findUpar(u);
  78.         int UparV = findUpar(v);
  79.         if (UparU == UparV)
  80.             return;
  81.         if (size[UparU] < size[UparV]) {
  82.             par[UparU] = UparV;
  83.             size[UparV] += size[UparU];
  84.         } else {
  85.             par[UparV] = UparU;
  86.             size[UparU] += size[UparV];
  87.         }
  88.     }
  89. };
  90.  
  91. void gon() {
  92.     int n, m;
  93.     cin >> n >> m;
  94.     adjs(v, int, n + 5);
  95.     vector<pi > ed;
  96.     for (int i = 0; i < m; i++) {
  97.         int l, r;
  98.         cin >> l >> r;
  99.         ed.push_back({min(l, r), max(l, r)});
  100.         v[l].push_back(r);
  101.         v[r].push_back(l);
  102.     }
  103.  
  104.     vector<int> dfn(n + 5, -1), lowlink(n + 5, -1);
  105.     timer = 1;
  106.     bridges.clear();
  107.     for (int i = 1; i <= n; i++) {
  108.         if (dfn[i] == -1) {
  109.             dfsSCC(i, -1, dfn, lowlink, v);
  110.         }
  111.     }
  112.     map<pi, int> mp;
  113.     for (auto i: bridges)
  114.         mp[i] = 1;
  115.     DSU d(n + 5);
  116.     for (auto i: ed) {
  117.         if (!mp.count(i)) {
  118.             d.unionbySize(i.first, i.second);
  119.         }
  120.     }
  121.     vector<int> comp(n + 5, 1e9);
  122.     for (int i = 1; i <= n; i++) {
  123.         comp[d.findUpar(i)] = min(comp[d.findUpar(i)], i);
  124.     }
  125.     vector<set<int >> mst(n + 5);
  126.     int cot = 0;
  127.     for (auto i: ed) {
  128.         if (!mp.count(i)) {
  129.             continue;
  130.         }
  131.         cot++;
  132.         int a = comp[d.findUpar(i.first)];
  133.         int b = comp[d.findUpar(i.second)];
  134.         mst[a].insert(b);
  135.         mst[b].insert(a);
  136.     }
  137.     int St = 1;
  138.     int last = 1;
  139.     int mx = 0;
  140.     int cur = 0;
  141.     vector<int> vis(n + 5);
  142.     dfs(St, mst, vis, last, mx, cur);
  143.     vis.assign(n + 5, 0);
  144.     int L = last;
  145.     St = last;
  146.     mx = 0;
  147.     cur = 0;
  148.     dfs(St, mst, vis, last, mx, cur);
  149.     cout << cot - mx << endl;
  150. }
  151.  
  152. int32_t main() {
  153.     killua;
  154.     int t = 1;
  155.     if (cases) cin >> t;
  156.     while (t--) {
  157.         gon();
  158.     }
  159. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/inMz6u
language:
C++14 (gcc 8.3)
created:
189 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!