SHARE
TWEET

Untitled

a guest Oct 9th, 2015 248 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top