[徐州网络赛][并查集]B-so easy

发布于 2019-09-19  191 次阅读


https://nanti.jisuanke.com/t/41384

比赛时WA到飞的一道题
题目:N个点从左到右为1--n 有两种操作
1. 让x点不可达
2.查询x(包括x)后第一个可达的点
用Map模拟并查集 删除一个点时 令x的父亲等于x+1的父亲 查询时直接输出x的父亲

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
unordered_map<int, int> fa;
int findfa(int x) {
    if (!fa.count(x)) return x;
    return fa[x] = findfa(fa[x]);
}
int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int n, q;
    scanf("%d %d", &n, &q);
    int op, x;
    while (q--) {
        scanf("%d %d", &op, &x);
        if (op == 1) {
            fa[x] = findfa(x + 1);
        } else {
            int ans = findfa(x);
            if (ans > n) ans = -1;
            printf("%d\n", ans);
        }
    }
    return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。