首页 > 代码库 > HDU 2473 Junk-Mail Filter 并查集，虚拟删除操作
HDU 2473 Junk-Mail Filter 并查集，虚拟删除操作
给定两种操作
第一种是合并X Y
第二种是把X分离出来，就是从原来的集合中分离出来，其它的关系不变。
关键是怎么分离，可以考虑把它变成一个其它值。HASH[i] = other_val
然后用新值去做并查集即可、
需要注意的一点就是
加入现在根是1，fa[1] = 1, fa[2] = 1, fa[3] = 1
那么如果你删除了1，这应该输出2.但是现在是fa[2] = 1，是一个不存在的根了，这个时候ans应该+1，但是按照并查集的思路
if (find(HASH[i]) == HASH[i]) ans++ 是不行的，因为这个根已经不存在了。
解决方法就是标记是否为虚根，del[i] = true表示删除了，但是枚举fa[3]的时候就要避免重新加，需要取消标记。
如果这时再有M 4 2，那么就把fa[4] = 1，用虚根表示即可。
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 2e6 + 20;int fa[maxn];int HASH[maxn];bool del[maxn];void init() { memset(del, 0, sizeof del); for (int i = 0; i < maxn; ++i) fa[i] = i; for (int i = 0; i < maxn; ++i) HASH[i] = i;}int find(int u) { if (fa[u] == u) return u; else return fa[u] = find(fa[u]);}void merge(int x, int y) { x = find(x); y = find(y); if (x != y) { fa[y] = x; }}int n, m;int ff;void work() { init(); int t = n; for (int i = 1; i <= m; ++i) { char str[11]; int a, b; scanf("%s", str); if (str[0] == ‘M‘) { scanf("%d%d", &a, &b); merge(HASH[a], HASH[b]); } else { scanf("%d", &a); del[HASH[a]] = 1; HASH[a] = n++; } } int ans = 0; for (int i = 0; i < t; ++i) { if (find(HASH[i]) == HASH[i]) ans++; if (del[find(HASH[i])]) { del[find(HASH[i])] = 0; ans++; } }// cout << find(2) << endl; printf("Case #%d: %d\n", ++ff, ans); return;}int main() {#ifdef local freopen("data.txt","r",stdin);#endif while (scanf("%d%d", &n, &m) != EOF && (n + m)) { work(); } return 0;}
HDU 2473 Junk-Mail Filter 并查集，虚拟删除操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。