SHARE
TWEET

Untitled

a guest Oct 9th, 2015 168 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
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top