「SCOI 2010」连续攻击游戏

题目大意：

匈牙利

#include <cstdio>

const int N = 2000005;
int head[N], nxt[N], v[N], tot, fa[N], vis[N], mx;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int max(int x, int y) {
    return x > y ? x : y;
}
void add_edge(int from, int to) {
    nxt[++tot] = head[from];
    head[from] = tot, v[tot] = to;
}
bool dfs(int u, int k) {
    for (int i = head[u]; i; i = nxt[i]) {
        if (vis[v[i]] == k) continue;
        vis[v[i]] = k;
        if (!fa[v[i]] || dfs(fa[v[i]], k)) {
            fa[v[i]] = u; return true;
        }
    }
    return false;
}

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        int x = read(), y = read();
        add_edge(x, i), add_edge(y, i);
        mx = max(mx, max(x, y));
    }
    for (int i = 1; i <= mx; ++i)
        if (!dfs(i, i)) {
            printf("%d\n", i - 1);
            return 0;
        }
    printf("%d\n", mx);
    return 0;
}

并查集

#include <cstdio>

const int N = 10005;
int fa[N], ok[N];

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void swap(int &x, int &y) {
    x ^= y, y ^= x, x ^= y;
}
int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}

int main() {
    int n = read();
    for (int i = 1; i <= 10000; ++i) fa[i] = i;
    for (int i = 1; i <= n; ++i) {
        int x = read(), y = read();
        int fx = find(x), fy = find(y);
        if (fx == fy) ok[fx] = 1;
        else {
            if (fx > fy) swap(fx, fy);
            if (ok[fx]) ok[fy] = 1;
            else ok[fx] = 1; //优先标记较小编号
            fa[fx] = fy; //令fa为较大编号, 以用于后面的合并
        }
    }
    for (int i = 1; i <= n + 1; ++i)
        if (!ok[i]) { printf("%d\n", i - 1); break; }
    return 0;
}