Guest User

Untitled

a guest
Oct 9th, 2015
363
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdio.h>
  4. using namespace std;
  5.  
  6. int T;
  7. int n,m;
  8.  
  9. bool bri[100100];
  10. vector<int> adj[100100];
  11. vector<int> ind[100100];
  12.  
  13. vector<int> adj2[100100];
  14.  
  15. int aa,bb;
  16. int r,c;
  17. int ra[100100],lw[100100];
  18. int co[100100];
  19. bool vis[100100];
  20. int cnt,sol;
  21. int dp[100100];
  22. void bridge(int nd,int p){
  23.     ra[nd]=r;
  24.     lw[nd]=r;
  25.     r++;
  26.     for(int i=0;i<adj[nd].size();i++){
  27.         int ch=adj[nd][i];
  28.         int id=ind[nd][i];
  29.         if(ch==p)continue;
  30.         if(ra[ch]==0){
  31.             bridge(ch,nd);
  32.             if(lw[ch]==ra[ch]){
  33.                 bri[id]=true;
  34.             }
  35.             lw[nd]=min(lw[nd],lw[ch]);
  36.         } else {
  37.             lw[nd]=min(lw[nd],ra[ch]);
  38.         }
  39.     }
  40. }
  41.  
  42. void comp(int nd){
  43.     vis[nd]=true;
  44.     co[nd]=c;
  45.     for(int i=0;i<adj[nd].size();i++){
  46.         int ch=adj[nd][i];
  47.         int id=ind[nd][i];
  48.         if(bri[id])continue;
  49.         if(vis[ch])continue;
  50.         comp(ch);
  51.     }
  52. }
  53.  
  54. void diameter(int nd,int p){
  55.     dp[nd]=0;
  56.  
  57.     int mx=-1,mx2=-1;
  58.     for(int i=0;i<adj2[nd].size();i++){
  59.         int ch=adj2[nd][i];
  60.         if(ch==p)continue;
  61.         diameter(ch,nd);
  62.         dp[nd]=max(dp[nd],dp[ch]+1);
  63.         if(dp[ch]>mx2){
  64.             mx2=dp[ch];
  65.         }
  66.         if(mx2>mx){
  67.             swap(mx2,mx);
  68.         }
  69.     }
  70.     sol=max(sol,mx2+mx+2);
  71. }
  72. int main(){
  73.     scanf("%d",&T);
  74.     while(T--){
  75.         scanf("%d %d",&n,&m);
  76.         cnt=0;
  77.         sol=0;
  78.         r=1;
  79.         c=1;
  80.         for(int i=1;i<=n;i++){
  81.             adj[i].clear();
  82.             adj2[i].clear();
  83.             ind[i].clear();
  84.             ra[i]=0;
  85.             lw[i]=0;
  86.             co[i]=0;
  87.             dp[i]=0;
  88.             vis[i]=false;
  89.         }
  90.         for(int i=1;i<=m;i++){
  91.             bri[i]=false;
  92.         }
  93.         for(int i=1;i<=m;i++){
  94.             scanf("%d %d",&aa,&bb);
  95.             adj[aa].push_back(bb);
  96.             adj[bb].push_back(aa);
  97.  
  98.             ind[aa].push_back(i);
  99.             ind[bb].push_back(i);
  100.         }
  101.         bridge(1,1);
  102.         for(int i=1;i<=n;i++){
  103.             if(!vis[i]){
  104.                 comp(i);
  105.                 c++;
  106.             }
  107.         }
  108.         c--;
  109.         for(int i=1;i<=n;i++){
  110.             for(int j=0;j<adj[i].size();j++){
  111.                 int ch=adj[i][j];
  112.                 int id=ind[i][j];
  113.                 if(bri[id]){
  114.                     cnt++;
  115.                     adj2[ co[i] ].push_back( co[ch] );
  116.                 }
  117.             }
  118.         }
  119.         cnt/=2;
  120.         diameter(1,1);
  121.         printf("%d\n",cnt-sol);
  122.     }
  123. }
RAW Paste Data