題意:
? ? ? 給你一個(gè)圖,問(wèn)你刪除一些邊后還有幾個(gè)連通快..


思路:

? ? ? 典型的并查集刪邊操作,并查集的刪邊就是先把不刪除的邊并查集一邊(本題沒(méi)有不刪除的邊),然后逆序吧所有要?jiǎng)h除的邊以點(diǎn)點(diǎn)加到并查集數(shù)組里,如果當(dāng)前的邊的兩個(gè)點(diǎn)不是一個(gè)集合的,那么刪除當(dāng)前邊后就會(huì)使連通快加一...

#include<stdio.h> #include<string.h>#define N 11000 typedef struct {int a ,b ,c; }EDGE;int mer[N]; EDGE E[N*10];int finds(int x) {return x == mer[x] ? x : mer[x] = finds(mer[x]); }int main () {int n ,m ,a ,b ,i;while(~scanf("%d %d" ,&n ,&m)){for(i = 1 ;i <= n ;i ++)mer[i] = i;for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&a ,&b);E[i].a = a + 1;E[i].b = b + 1;}int sum = n;for(i = m;i >= 1;i --){a = finds(E[i].a);b = finds(E[i].b);E[i].c = sum;if(a != b) sum --;mer[a] = b;} for(i = 1 ;i <= m ;i ++)printf("%d\n" ,E[i].c); }return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4496并查集的删边操作的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。