猴子问题

(monkey.pas/c/cpp)

【问题描述】

树上有n只猴子，它们编号为1~n。1号猴子用它的尾巴勾住一根树枝，其他的猴子有的被别的猴子抓住，有的抓住别的猴子，有的同时抓与被抓……每只猴子可以用它们的两只手，每只手至多抓住一只猴子。从0时刻开始，每秒会有一只猴子松开它的一只手。这也许会导致一些猴子掉到地上（猴子掉到地上也可以松手，掉落的时间忽略不计）。

    任务：

    编写一个程序完成：

    从输入中读取初始状态猴子如何挂在一起，以及猴子们松手的顺序；输出每只猴子掉到地上的时间。

【输入】

    输入的第一行包含两个正整数n和m，1 <= n <= 200000, 1 <= m <= 400000。n表示猴子的数量，m表示从0~m-1时刻每时刻有一只猴子松开它的一只手。接下来的n行描述猴子的初始状态。在第k+1行有两个正整数表示k号猴子两只手的情况：前一个数表示左手抓的猴子编号，后一个数表示右手抓的猴子编号，若为-1则该手是空的。接下来m行表示猴子松手的情况。每行有两个正整数a，b，表示a号猴子在该时刻放开它的一只手（b=1为左手，b=2为右手）。

【输出】

你的程序需要输出n个整数，每行一个。第i行的整数表示第i只猴子在何时刻掉到地上。若这只猴子不会掉到地上，则用-1表示。

【输入输出样例】

【样例说明】

   初始状态为1号抓3号，2号抓3号，3号抓1号，3号抓2号。

   0时刻1号松左手，此时2号抓3号，3号抓1号，3号抓2号。

   1时刻3号松左手，此时3号抓2号，2号抓3号。由于2、3号都不与1号相连，所以两只猴子在1时刻掉到地上。

【数据范围】

    数据编号       N        M

   1         10000     9999

   2          100      106

   3          500      923

   4         1000      1600

   5         10000     19631

   6         20000     40000

   7         50000     100000

   8         100000    200000

   9         150000    270000

   10        200000    400000

【题解】

嗯很容易发现是要倒着做

那就是一个并查集的事情啦~

什么时候掉下来就是什么时候接到根（1）上

但是更新的时候是要更新一整个连通块

所以呢就要用边链表

合并的时候顺便合并边链表咯

一遍写完过样例好爽QAQ

# include <stdio.h>
# include <queue>
# include <stdlib.h>
# include <string.h>
using namespace std;
int fa[500010];
int n, m;
int left[500010], right[500010];
bool ll[500010], rr[500010];
int qa[500010], qb[500010];
int head[1000010], next[1000010], to[1000010], tot=0, vis[500010], ans[500010];
inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}
inline void link(int u, int v) {
	add(u,v);
	add(v,u);
}
queue<int> q;
inline void bfs(int start, int vv) {
	while(!q.empty()) q.pop();
	q.push(start);
	vis[start] = vv;
	while(!q.empty()) {
		int top = q.front();
		q.pop();
		ans[top] = vv-1;
		for (int i=head[top]; i; i=next[i]) {
			if(vv != vis[to[i]]) {
				vis[to[i]] = vv;
				q.push(to[i]);
			}
		}
	}
}
int main() {
	freopen("monkey.in", "r", stdin);
	freopen("monkey.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i)
		scanf("%d%d", &left[i], &right[i]);
	for (int i=1; i<=m; ++i) {
		scanf("%d%d", &qa[i], &qb[i]);
		if(qb[i] == 1) ll[qa[i]] = 1;
		else rr[qa[i]] = 1;
	}
	for (int i=1; i<=n; ++i) fa[i] = i;
	int fu, fv, a, b, fw;
	for (int i=1; i<=n; ++i) {
		if(!ll[i] && left[i] != -1) {
			fu = getf(i), fv = getf(left[i]);
			if(fu != fv) {
				fa[fu] = fv;
				link(fu, fv);
			}
		}
		if(!rr[i] && right[i] != -1) {
			fu = getf(i), fv = getf(right[i]);
			if(fu != fv) {
				fa[fu] = fv;
				link(fu, fv);
			}
		}
	}
	for (int i=1; i<=n; ++i)
		ans[i] = -1;
	for (int i=m; i>=1; --i) {
		a = qa[i];
		if(qb[i] == 1) {
			if(left[qa[i]] != -1) b = left[qa[i]];
			else continue;
		} else {
			if(right[qa[i]] != -1) b = right[qa[i]];
			else continue;
		}
		fu = getf(a), fv = getf(b);
		fw = getf(1);
		if(fu == fw && fv != fw) {
			bfs(fv, i);
			fa[fv] = fw;
			link(fv, fw);
		} else if(fu != fw && fv == fw) {
			bfs(fu, i);
			fa[fu] = fw;
			link(fu, fw);
		} else if(fu != fv) {
			fa[fu] = fv;
			link(fu, fv);
		}
	}
	//ans[1] = -1;
	for (int i=1; i<=n; ++i) printf("%d\n", ans[i]);
	return 0;
}