fork download
copy 
  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. vector<int> adj[maxV];
  19. vector<int> adj1[maxV];
  20. ll disc[maxV];
  21. ll low[maxV];
  22. set<pii> ans;
  23. ll cnt;
  24.  
  25. struct subset
  26. {
  27.     int parent;
  28.     int rank;
  29. }subsets[maxV];
  30.  
  31. void initialize()
  32. {
  33.     memset(visited,0,sizeof(visited));
  34.     memset(parent,-1,sizeof(parent));
  35. }
  36.  
  37. void initializer(int V)
  38. {
  39.     REP(i,1,V+1)
  40.     {
  41.         subsets[i].parent=i;
  42.         subsets[i].rank=0;
  43.     }
  44. }
  45.  
  46. void bridge(int u)
  47. {
  48.     static ll time = 0;
  49.     visited[u] = 1;
  50.     disc[u] = low[u] = ++time;
  51.     iter(i,adj[u])
  52.     {
  53.         int v = *i;
  54.         if (!visited[v])
  55.         {
  56.             parent[v] = u;
  57.             bridge(v);
  58.             low[u]=min(low[u],low[v]);
  59.             if (low[v] > disc[u])
  60.               cnt++,ans.insert(mkp(u,v)),ans.insert(mkp(v,u));
  61.         }
  62.         else if (v != parent[u])
  63.             low[u]=min(low[u],disc[v]);
  64.     }
  65. }
  66.  
  67. void dfs(int s,ll dis)
  68. {
  69.     visited[s]=dis;
  70.     iter(i,adj1[s])
  71.         if(visited[*i]==-1)
  72.             dfs(*i,dis+1);
  73. }
  74.  
  75. int find(int x)
  76. {
  77.     if(subsets[x].parent!=x)
  78.         subsets[x].parent=find(subsets[x].parent);
  79.     return subsets[x].parent;
  80. }
  81.  
  82. void Union(int x,int y)
  83. {
  84.     int xroot=find(x);
  85.     int yroot=find(y);
  86.  
  87.     if(subsets[xroot].rank>subsets[yroot].rank)
  88.         subsets[yroot].parent=xroot;
  89.     else if(subsets[xroot].rank<subsets[yroot].rank)
  90.         subsets[xroot].parent=yroot;
  91.     else
  92.         subsets[xroot].parent=yroot,subsets[yroot].rank++;
  93. }
  94.  
  95. void DSU(int n)
  96. {
  97.     REP(i,1,n+1)
  98.     {
  99.         REP(j,0,adj[i].size())
  100.         {
  101.             if(ans.find(pii(i,adj[i][j]))==ans.end())
  102.             {
  103.                 int xroot=find(i);
  104.                 int yroot=find(adj[i][j]);
  105.                 if(xroot!=yroot)
  106.                     Union(xroot,yroot);
  107.             }
  108.         }
  109.     }
  110. }
  111.  
  112. int main() {
  113. 	ios_base::sync_with_stdio(false);
  114. 	cin.tie(NULL);
  115.     int t,a,b,n,m;
  116.     cin>>t;
  117.     while(t--)
  118.     {
  119.         ll maxi=-1;
  120.         cnt=0;
  121.         cin>>n>>m;
  122.         REP(i,0,maxV)
  123.             adj[i].clear(),adj1[i].clear();
  124.         ans.clear();
  125.         REP(i,0,m)
  126.         {
  127.             cin>>a>>b;
  128.             adj[a].pb(b);
  129.             adj[b].pb(a);
  130.         }
  131.         initialize();
  132.         REP(i,1,n+1)
  133.         if(!visited[i])
  134.             bridge(i);
  135.         initializer(n);
  136.         DSU(n);
  137.         iter(i,ans)
  138.         {
  139.             pii p;
  140.             p.fst=i->fst;
  141.             p.snd=i->snd;
  142.             if(find(p.fst)!=find(p.snd))adj1[find(p.fst)].pb(find(p.snd));
  143.         }
  144.         memset(visited,-1,sizeof(visited));
  145.         REP(i,1,n+1)
  146.             if(visited[i]==-1)
  147.                 dfs(i,0LL);
  148.         REP(i,1,n+1)
  149.             maxi=max(maxi,visited[i]);
  150.         cout<<cnt-maxi<<endl;
  151.     }
  152. 	return 0;
  153. }
  154.  
Success #stdin #stdout 0.01s 9320KB
comments (?)
stdin
copy 
2
7 7
1 2
2 3
3 1
3 4
4 5
4 6
6 7
3 3
1 2
2 3
3 1
stdout
copy 
1
0
https://ideone.com/XNdmzK
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!