首页 > 代码库 > 并查集
并查集
POJ 1182 食物链
添加一个维护当前节点与父节点关系的信息，每次压缩时更新关系，另外join的时候也要根据当前节点和父节点关系以及两个父节点关系更新；
单case，不用EOF处理。
# include <cstdio>const int maxn = 50005;int n, k;int p[maxn];int g[maxn];int find(int x) { if (x == p[x]) return x; int t = find(p[x]); g[x] = ((g[p[x]] + g[x]) % 3 + 3) % 3; p[x] = t; return t;}# define testin freopen("in.txt", "r", stdin)int main(){ //while (scanf("%d%d", &n, &k) != EOF) { scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) p[i] = i, g[i] = 0; int ans = 0; for (int i = 0, od, x, y; i < k; ++i) { scanf("%d%d%d", &od, &x, &y); if (x>n||y>n || (od==2 && x==y)) { ++ans; continue; } else { int fx = find(x); int fy = find(y); if (fx != fy) { p[fx] = fy; g[fx] = ((g[y]-g[x]+od-1)%3+3)%3; } else if (((g[x]-g[y])%3+3)%3 != od-1){ ++ans; } } } printf("%d\n", ans); //} return 0;}
HDU 2473
带删除节点的并查集
对每个节点，映射射到一个虚拟节点，然后对虚拟节点维护并查集，删除节点时，将对应节点应射到一个新的节点即可，由于查询次数有限，浪费的空间可以接受。
# include <cstdio>const int maxn = 100005;const int maxm = 1000005;int n, m;int fa[maxn + maxm];bool isRoot[maxn + maxm];int link[maxn];int id;int find(int x) { if (x != fa[x]) return fa[x]=find(fa[x]);}void join(int x, int y){ x = find(x); y = find(y); if (x != y) fa[x] = y;}void del(int x){ link[x] = id++;}# define testin freopen("in.txt", "r", stdin)int main(){ int ica = 0; while (scanf("%d%d", &n, &m), n||m) { for (int i = 0; i < n+m; ++i) isRoot[i]=false, fa[i]=i; for (int i = 0; i < n; ++i) link[i] = i; char od[5]; id = n; for (int i = 0, x, y; i < m; ++i) { scanf("%s%d", od, &x); if (od[0] == ‘M‘) { scanf("%d", &y); join(link[x], link[y]); } else { del(x); } } int ans = 0; for (int i = 0; i < n; ++i) { if (!isRoot[ find(link[i]) ]) { ++ans; isRoot[ find(link[i]) ] = true; } } printf("Case #%d: %d\n", ++ica, ans); } return 0;}
ZOJ 3261
带删除边的并查集。
WA：维护的并不是树，每个节点和多个节点直接有关系，不能直接删除并查集中的边。
并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。