fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. int n,m ,low[100001],num[100001],par[100001],id,T,comid,com_id[100001];
  5. map<pair<int,int>,bool>there;
  6. bool vis[100001];
  7. vector<vector<int> > v;
  8. vector<pair<int,int> >edges;    
  9. void dfs(int u){
  10.     num[u]=low[u]=++id;
  11.     vis[u]=1;
  12.     for(int i=0;i<v[u].size();++i){
  13.         int node=v[u][i];
  14.  
  15.         if(!vis[node]){
  16.  
  17.         	par[node]=u;
  18.             dfs(node);
  19.             low[u]=min(low[node],low[u]);
  20.           if (low[node] > num[u])
  21.             {        
  22.                 there[make_pair(node,u)]=1;
  23.                 there[make_pair(u,node)]=1;
  24.             }
  25.         }
  26.         else if(node!=par[u])
  27.         low[u]=min(low[u],num[node]);
  28.     }
  29. }
  30. void dfs2(int x){
  31.     vis[x]=1;
  32.     com_id[x]=comid;
  33.     for(int i=0;i<v[x].size();++i){
  34.         int y=v[x][i];
  35.         if(!vis[y])
  36.         {
  37.             dfs(y);
  38.         }
  39.     }
  40. }
  41. int mxlen,mxnode;
  42. void dfs3(int x,int p,int cost){
  43.     if(cost>mxlen)
  44.     mxlen=cost,mxnode=x;
  45.     for(int i=0;i<v[x].size();++i)
  46.         if(v[x][i]!=p)
  47.             dfs3(v[x][i],x,cost+1);
  48. }
  49. int main(){
  50.     scanf("%d",&T);
  51.     while(T--){
  52.         scanf("%d%d",&n,&m);
  53.         v.resize(n);
  54.         for(int i=0,a,b;i<m;++i)  {
  55.             scanf("%d%d",&a,&b);
  56.             --a;--b;
  57.             v[a].push_back(b);
  58.             v[b].push_back(a);
  59.             edges.push_back(make_pair(a,b));
  60.         }      
  61.         dfs(0);
  62.         v.clear();
  63.         v.resize(n);
  64.         vector<pair<int,int> > B;
  65.         for(int i=0;i<m;++i)
  66.         {
  67.             int a=edges[i].first;
  68.             int b=edges[i].second;
  69.             if(!there[make_pair(edges[i].first,edges[i].second)])
  70.             {
  71.                  v[a].push_back(b);
  72.                  v[b].push_back(a);
  73.             }else{
  74.                 B.push_back(make_pair(a,b));
  75.             }
  76.         }
  77.  
  78.         memset(vis,0,sizeof vis);
  79.         for(int i=0;i<n;++i){
  80.             if(!vis[i]){
  81.                 dfs2(i);
  82.                 ++comid;
  83.             }
  84.         }
  85.         v.clear();
  86.         v.resize(comid);
  87.         for(int i=0;i<B.size();++i){
  88.             int a=com_id[B[i].first];
  89.             int b=com_id[B[i].second];
  90.             v[a].push_back(b);
  91.             v[b].push_back(a);
  92.         }
  93.         dfs3(0,-1,0);
  94.         mxlen=0;
  95.         dfs3(mxnode,-1,0);
  96.         memset(vis,0,sizeof vis);
  97.         memset(par,-1,sizeof par);
  98.         memset(num,0,sizeof num);
  99.         memset(com_id,0,sizeof com_id);
  100.         memset(low,0,sizeof low);
  101.         id=0;
  102.  
  103.         comid=0;
  104.         there.clear();
  105.         v.clear();
  106.         edges.clear();
  107.         mxlen=0;
  108.         mxnode=0;
  109.  
  110.     }   
  111. }
Success #stdin #stdout 0s 5136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/86zKZk
language:
C++14 (gcc 8.3)
created:
8 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!