HDU 4496 D-City (并查集)

题意:给定一个图,问你每次删除一条边后有几个连通块。

析:水题,就是并查集的运用,倒着推。

代码如下:

#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
using namespace std ;
typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1e4 + 5;
const int dr[] = {0, 0, -1, 1};
const int dc[] = {-1, 1, 0, 0};
int n, m;
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
int p[maxn];
int e1[maxn*10], e2[maxn*10];
int Find(int x){ return x == p[x] ? x : p[x] = Find(p[x]); }
int ans[maxn*10]; int main(){
while(scanf("%d %d", &n, &m) == 2){
for(int i = 0; i < n; ++i) p[i] = i; for(int i = 0; i < m; ++i)
scanf("%d %d", &e1[i], &e2[i]); int cnt = n;
for(int i = m-1; i >= 0; --i){
ans[i] = cnt;
int x = Find(e1[i]);
int y = Find(e2[i]);
if(x != y){
p[y] = x;
--cnt;
}
} for(int i = 0; i < m; ++i)
printf("%d\n", ans[i]);
}
return 0;
}
上一篇:HDU -- 4496


下一篇:hdu 4496 D-City(并查集)