fork(5) download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long int
  6. #define iter(i,a) for( typeof(a.begin()) i=a.begin();i!=a.end();i++)
  7. #define REP(p,a,b) for(int p=a;p<b;p++)
  8. #define pb(f) push_back(f)
  9. #define mkp(a,b) make_pair(a,b)
  10. #define fst first
  11. #define snd second
  12. #define pii pair<int,int>
  13. #define ins(a) insert(a)
  14. #define maxV 100005
  15.  
  16. ll visited[maxV];
  17. int parent[maxV];
  18. ll longest;
  19. vector<int> adj[maxV];
  20. vector<int> adj1[maxV];
  21. ll disc[maxV];
  22. ll low[maxV];
  23. ll best[maxV][2];
  24. set<pii> ans;
  25. ll cnt;
  26.  
  27. struct subset
  28. {
  29.     int parent;
  30.     int rank;
  31. }subsets[maxV];
  32.  
  33. void initialize()
  34. {
  35.     memset(visited,0,sizeof(visited));
  36.     memset(parent,-1,sizeof(parent));
  37. }
  38.  
  39. void initializer(int V)
  40. {
  41.     REP(i,1,V+1)
  42.     {
  43.         subsets[i].parent=i;
  44.         subsets[i].rank=0;
  45.     }
  46. }
  47.  
  48. void bridge(int u)
  49. {
  50.     static ll time = 0;
  51.     visited[u] = 1;
  52.     disc[u] = low[u] = ++time;
  53.     iter(i,adj[u])
  54.     {
  55.         int v = *i;
  56.         if (!visited[v])
  57.         {
  58.             parent[v] = u;
  59.             bridge(v);
  60.             low[u]=min(low[u],low[v]);
  61.             if (low[v] > disc[u])
  62.               cnt++,ans.insert(mkp(u,v)),ans.insert(mkp(v,u));
  63.         }
  64.         else if (v != parent[u])
  65.             low[u]=min(low[u],disc[v]);
  66.     }
  67. }
  68.  
  69. void dfs(int v)
  70. {
  71.     visited[v]=1;
  72.     int n=adj1[v].size();
  73.     for (int i=0;i<n;i++)
  74.     {
  75.         int u=adj1[v][i];
  76.         if (visited[u])
  77.             continue;
  78.         dfs(u);
  79.         if (best[u][0]+1>best[v][0])
  80.         {
  81.             best[v][1]=best[v][0];
  82.             best[v][0]=best[u][0]+1;
  83.         }
  84.         else if (best[u][0]+1>best[v][1])
  85.             best[v][1]=best[u][0]+1;
  86.     }
  87.     longest=max(longest,best[v][0]+best[v][1]);
  88. }
  89.  
  90. int find(int x)
  91. {
  92.     if(subsets[x].parent!=x)
  93.         subsets[x].parent=find(subsets[x].parent);
  94.     return subsets[x].parent;
  95. }
  96.  
  97. void Union(int x,int y)
  98. {
  99.     int xroot=find(x);
  100.     int yroot=find(y);
  101.  
  102.     if(subsets[xroot].rank>subsets[yroot].rank)
  103.         subsets[yroot].parent=xroot;
  104.     else if(subsets[xroot].rank<subsets[yroot].rank)
  105.         subsets[xroot].parent=yroot;
  106.     else
  107.         subsets[xroot].parent=yroot,subsets[yroot].rank++;
  108. }
  109.  
  110. void DSU(int n)
  111. {
  112.     REP(i,1,n+1)
  113.     {
  114.         REP(j,0,adj[i].size())
  115.         {
  116.             if(ans.find(pii(i,adj[i][j]))==ans.end())
  117.             {
  118.                 int xroot=find(i);
  119.                 int yroot=find(adj[i][j]);
  120.                 if(xroot!=yroot)
  121.                     Union(xroot,yroot);
  122.             }
  123.         }
  124.     }
  125. }
  126.  
  127. int main() {
  128.     ios_base::sync_with_stdio(false);
  129.     cin.tie(NULL);
  130.     int t,a,b,n,m;
  131.     cin>>t;
  132.     while(t--)
  133.     {
  134.         ll maxi=-1;
  135.         cnt=0;
  136.         cin>>n>>m;
  137.         REP(i,0,maxV)
  138.             adj[i].clear(),adj1[i].clear(),best[i][0]=best[i][1]=0;
  139.         ans.clear();
  140.         REP(i,0,m)
  141.         {
  142.             cin>>a>>b;
  143.             adj[a].pb(b);
  144.             adj[b].pb(a);
  145.         }
  146.         initialize();
  147.         REP(i,1,n+1)
  148.         if(!visited[i])
  149.             bridge(i);
  150.         initializer(n);
  151.         longest=0;
  152.         DSU(n);
  153.         iter(i,ans)
  154.         {
  155.             pii p;
  156.             p.fst=i->fst;
  157.             p.snd=i->snd;
  158.             if(find(p.fst)!=find(p.snd))
  159.                 adj1[find(p.fst)].pb(find(p.snd));
  160.         }
  161.         memset(visited,0,sizeof(visited));
  162.         for (int i=1;i<=n;i++)
  163.         {
  164.             if (!visited[i])
  165.                 dfs(i);
  166.         }
  167.         cout<<cnt-longest<<endl;
  168.     }
  169.     return 0;
  170. }
Runtime error #stdin #stdout 0s 10880KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/duttRl
language:
C++14 (gcc 8.3)
created:
9 years 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!