P8059 [POI2003] Monkeys

Alex_Wei · 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;
}