首页 > 代码库 > hdu--4496--并查集

hdu--4496--并查集

好久没写并查集了 还好这题蛮水的~

从前到后的删除 那我就先将所有的边给记录下来 然后从后往前的添加边 就是同一个意思了.离线处理吧相当于 一次性全部输出

有点逆序的味道~~

-----但我闻到了风中 苦涩的味道 哈哈~~

 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4  5 int n; 6 const int size = 10100; 7 int father[size] , ans[size*10] , from[size*10] , to[size*10]; 8  9 int find( int x )10 {11     return father[x] == -1 ? x : father[x] = find( father[x] );12 }13 14 int main()15 {16     int m , sum , x , y;17     while( ~scanf("%d%d",&n,&m) )18     {19         sum = n;20         memset( father , -1 , sizeof(father) );21         for( int i = 0 ; i<m ; i++ )22         {23             scanf("%d%d",&from[i],&to[i]);24         }25         for( int i =  m-1 ; i>=0 ; i-- )26         {27             ans[i] = sum;28             x = find( from[i] );29             y = find( to[i] );30             if( x!=y )31             {32                 -- sum;33                 father[x] = y;34             }    35         }36         for( int i = 0 ; i<m ; i++ )37         {38             printf("%d\n",ans[i]);39         }40     }41     return 0;42 }
View Code

 

 

today:

  在拥挤的人群中

  感到光荣

hdu--4496--并查集