fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+1;
  4. int n,m,dfs_time,id,mxlen=-1,mxnode=-1,par[N],low[N],num[N],com[N];
  5. bool vis[N];
  6. vector<vector<int> > tree,g;
  7. vector<pair<int,int> > e;
  8. map<pair<int,int>,bool>b;
  9. void tar(int v){
  10.     vis[v]=1;
  11.     low[v]=num[v]=++dfs_time;
  12.     for(int i=0;i<g[v].size();++i){
  13.         int u=g[v][i];
  14.         if(!vis[u]){
  15.             par[u]=v;
  16.             tar(u);
  17.             low[v]=min(low[u],low[v]);
  18.             if(low[u]>num[v]){
  19.                 b[make_pair(u,v)]=b[make_pair(v,u)]=true;
  20.                 e.push_back(make_pair(u,v));
  21.             }
  22.         }
  23.         else if(par[v]!=u)
  24.         low[v]=min(num[u],low[v]);
  25.  
  26.     }
  27. }
  28. void dfs(int x){
  29.     vis[x]=1;
  30.     com[x]=id;
  31.     for(int i=0;i<g[x].size();++i)
  32.     if(!vis[g[x][i]]&& !b[make_pair(x,g[x][i])])
  33.     dfs(g[x][i]);
  34. }
  35. void longest_path(int x,int p,int cost){
  36.     if(mxlen<cost)
  37.     mxlen=cost,mxnode=x;
  38.     for(int i=0;i<tree[x].size();++i){
  39.         if(tree[x][i]!=p)
  40.         longest_path(tree[x][i],x,cost+1);
  41.     }
  42. }
  43. void clear(){
  44.     memset(vis,0,sizeof vis);
  45.     memset(low,0,sizeof low);
  46.     memset(num,0,sizeof num);
  47.     memset(par,-1,sizeof par);
  48.     memset(com,-1,sizeof com);
  49.     mxlen=-1,mxnode=-1;
  50.     id=0;
  51.     dfs_time=0;
  52.     g.clear();
  53.     tree.clear();
  54.     b.clear();
  55.     e.clear();
  56.     }
  57. int main(){
  58.     int ts;
  59.     scanf("%d",&ts);
  60.     while(ts--){
  61.     scanf("%d%d",&n,&m);
  62.     g.resize(n);
  63.  
  64.     for(int i=0;i<m;++i){
  65.         int a,b;
  66.         scanf("%d%d",&a,&b);
  67.         --a;--b;
  68.         g[a].push_back(b);
  69.         g[b].push_back(a);
  70.  
  71.     }
  72.     tar(0);
  73.     memset(vis,0,sizeof vis);
  74.     for(int i=0;i<n;++i){
  75.         if(!vis[i])
  76.         {
  77.             dfs(i);
  78.             ++id;
  79.         }
  80.     }
  81.     tree.resize(id);
  82.     for(int i=0;i<e.size();++i){
  83.         int a=com[e[i].first];
  84.         int b=com[e[i].second];
  85.         tree[a].push_back(b);
  86.         tree[b].push_back(a);
  87.     }
  88.    // cout<<e.size()<<endl;
  89.     longest_path(0,-1,0);
  90.     mxlen=-1;
  91.     longest_path(mxnode,-1,0);
  92.     if(e.size()==0)
  93.     puts("0");
  94.     else
  95.     printf("%d\n",e.size()-mxlen);
  96.     clear();
  97.     }
  98.  
  99. }
  100.  
Success #stdin #stdout 0s 5140KB
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/QIYU0x
language:
C++14 (gcc 8.3)
created:
7 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!