首页 > 代码库 > 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 }
today:
在拥挤的人群中
感到光荣
hdu--4496--并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。