【洛谷 P1653】猴子（并查集）

题目链接

没删除调试输出，原地炸裂，\(80\)->\(0\)。如果你要问剩下的\(20\)呢？答：数组开小了。

这题正向删边判连通性是很不好做的，因为我们并不会并查集的逆操作。于是可以考虑把断边改成逆向连边，某个猴子什么时候和\(1\)号猴子变成连通的，这就是他掉下去的时间，如果本来就与\(1\)号猴子连通，那么它就永远不会掉下去。我用了两个并查集，一个维护连通性，一个维护答案，这两个并查集前面的操作几乎是一模一样的，同时连边，到最后一步也就是某个猴子与\(1\)号猴子变为连通时，前者正常连边，后者不连，因为我们要记录原连通块里的猴子答案是一样的。然后就\(ok\)了。

#include <cstdio>

#include <cstring>

#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);

#define Close fclose(stdin);fclose(stdout);

const int MAXN = 500010;

inline int read(){

	int s = 0, w = 1;

	char ch = getchar();

	while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }

	return s * w;

}

int n, m;

int a[MAXN], b[MAXN], f[MAXN], ban[MAXN][3], F[MAXN];

int fall_time[MAXN], son[MAXN][3], start_set[MAXN], linked[MAXN];

int junk;

void init(){

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

		f[i] = i;

}

int find(int x){

	return f[x] == x ? x : f[x] = find(f[x]);

}

void merge(int x, int y){

	f[find(y)] = find(x);

}

void Init(){

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

		F[i] = i;

}

int Find(int x){

	return F[x] == x ? x : F[x] = Find(F[x]);

}

void Merge(int x, int y){

	F[Find(y)] = Find(x);

}

int main(){

	Open("monkey");

	memset(fall_time, -1, sizeof fall_time);

	n = read(); m = read();

	init(); Init();

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

		son[i][1] = read(); son[i][2] = read();

	}

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

		a[i] = read(); b[i] = read();

		ban[a[i]][b[i]] = 1;

	}

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

		for(int j = 1; j <= 2; ++j)

			if(!ban[i][j])

				if(son[i][j] != -1)

					merge(i, son[i][j]), Merge(i, son[i][j]);

	for(int i = m; i; --i){

		junk = son[a[i]][b[i]];

		int fa = find(a[i]) != find(1), fb = find(junk) != find(1);

		merge(a[i], junk);

		if(fa && find(a[i]) == find(1))

			fall_time[Find(a[i])] = i - 1;

		else if(fa) Merge(a[i], junk);

		if(fb && find(junk) == find(1))

			fall_time[Find(junk)] = i - 1;

		else if(fb) Merge(a[i], junk);

	}

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

		printf("%d\n", fall_time[Find(i)]);

	Close;

	return 0;

}

巴特西

【洛谷 P1653】猴子（并查集）

最新文章

热门文章

巴特西

【洛谷 P1653】 猴子 （并查集）

最新文章

热门文章

【洛谷 P1653】猴子（并查集）