自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:35:35，当前版本为作者最后更新于2022-02-01 18:23:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8059 [POI2003] Monkeys

POI 合集。

连通性相关删边题目考虑时光倒流，求出每个猴子第一次与 $1$ 连通的时间。直接 dfs 打标记即可。时间复杂度线性，细节见代码。

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 5;
int n, m, ls[N], rs[N], ban[N][2];
int id[N], dir[N], ans[N], vis[N];
vector <pair <int, int>> e[N];
void dfs(int id, int as) {
	if(id == -1 || vis[id]) return; // vis[id] = 1 表示 id 与 1 连通
	vis[id] = 1, ans[id] = as; // ans[id] 表示 id 的答案
	if(!ban[id][0]) dfs(ls[id], as);
	if(!ban[id][1]) dfs(rs[id], as);
	for(auto it : e[id]) if(!ban[it.first][it.second]) dfs(it.first, as);
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> ls[i] >> rs[i];
		if(ls[i] != -1) e[ls[i]].push_back({i, 0}); // 连双向边，记录是哪只手
		if(rs[i] != -1) e[rs[i]].push_back({i, 1});
	} for(int i = 0; i < m; i++) cin >> id[i] >> dir[i], ban[id[i]][--dir[i]] = 1;
	dfs(1, -1);
	for(int i = m - 1; ~i; i--) {
		ban[id[i]][dir[i]] = 0;
		if(vis[id[i]]) dfs(dir[i] ? rs[id[i]] : ls[id[i]], i);
		if(vis[dir[i] ? rs[id[i]] : ls[id[i]]]) dfs(id[i], i);
	} for(int i = 1; i <= n; i++) cout << ans[i] << "\n";
	return 0;
}