Guest User

Untitled

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