HDU 4496 D-City (并查集)
HDU 查集 City
2023-09-11 14:17:18 时间
题意:给定一个图,问你每次删除一条边后有几个连通块。
析:水题,就是并查集的运用,倒着推。
代码如下:
#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 1671 Phone List 统计前缀次数
- hdu 1811Rank of Tetris (并查集 + 拓扑排序)
- HDU 1069 Monkey and Banana(动态规划)
- HDU 3442 Three Kingdoms(状态压缩 + BFS )
- 【hdu 2108】Shape of HDU
- HDU 1272: 小希的迷宫(并查集)
- hdu 5087 Revenge of LIS II ( LIS ,第二长子序列)
- hdu 2052 Picture(java)
- HDU 3622 Bomb Game(2-sat)
- HDU 2048 号码塔(DP)
- HDU 1248 冰封王座(dp)
- hdu 4961 Boring Sum(数学题)
- POJ 3691 & HDU 2457 DNA repair (AC自己主动机,DP)
- HDU 2853 Assignment(KM最大匹配好题)
- HDU 4939 Stupid Tower Defense dp
- HDU-1053-Entropy(Huffman编码)
- HDU 1423 Greatest Common Increasing Subsequence(最长公共上升LCIS)