题意：

每次合并两份邮件，或者将某一份邮件独立出来，问最后有多少个邮件集合。

分析：

考虑初始化每个节点的祖先为一个虚父节点(i + n)，虚父节点指向它自己。这样可以进行正常的合并操作。

而在删除时，将该节点的祖先置为一个更大的数(++anc_cnt)，并让该anc_cnt指向它自己，这样不会影响与自身节点相连的所有关系。最后统计有多少个不同的祖先即可。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, M = 1e6 + 5;

int n, anc[N * 12], x, y, vt, k, m, anc_cnt, ans, vst[N * 12];

char opt[5];

inline int getAnc(int x){return x == anc[x] ? x : (anc[x] = getAnc(anc[x]));}

inline void merge(int x, int y){

	int fx = getAnc(x), fy = getAnc(y);

	if(fx != fy) anc[fx] = fy;

}

inline void del(int x){anc[x] = ++anc_cnt; anc[anc_cnt] = anc_cnt;}

int main(){

	freopen("h.in", "r", stdin);

	while(scanf("%d%d", &n, &m) && (n + m)){

		for(int i = 1; i <= n; i++) anc[i] = i + n, anc[i + n] = i + n;

		anc_cnt = n * 2, ans = 0; vt++;

		for(int i = 1; i <= m; i++){

			scanf("%s", opt + 1);

			if(opt[1] == 'M'){

				scanf("%d%d", &x, &y);

				x++, y++;

				merge(x, y);

			}

			else{

				scanf("%d", &x);

				x++;

				del(x);

			}

		}

		for(int i = 1; i <= n; i++){

			int f = getAnc(i);

			if(vst[f] != vt) ans++;

			vst[f] = vt;

		}

		printf("Case #%d: %d\n", ++k, ans);

	}

	return 0;

}

巴特西

HDU2473 Junk-Mail Filter - 并查集删除操作(虚父节点)

题意：

分析：

code

最新文章

热门文章