洛谷P3144 [USACO16OPEN]Closing the Farm S 题解 并查集

题目链接：https://www.luogu.com.cn/problem/P3144

解题思路：

每次多去掉一个点，然后剩下的点进行并查集，并判断剩下的点是否属于同一个集合当中。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3030;
int n, m, f[maxn], a[maxn];
struct Edge {
    int u, v;
} edge[maxn];
void init() {
    for (int i = 1; i <= n; i ++) f[i] = i;
}
int Find(int x) {
    return x == f[x] ? x : f[x] = Find(f[x]);
}
void Union(int x, int y) {
    int a = Find(x), b = Find(y);
    f[a] = f[b] = f[x] = f[y] = min(a, b);
}
bool used[maxn];
bool solve(int id) {
    for (int i = 1; i < id; i ++) used[a[i]] = false;
    for (int i = id; i <= n; i ++) used[a[i]] = true;
    init();
    for (int i = 0; i < m; i ++) {
        int u = edge[i].u, v = edge[i].v;
        if (!used[u] || !used[v]) continue;
        Union(u, v);
    }
    for (int i = id+1; i <= n; i ++)
        if (Find(a[i]) != Find(a[id]))
            return false;
    return true;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++) cin >> edge[i].u >> edge[i].v;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++)
        puts(solve(i) ? "YES" : "NO");
    return 0;
}

洛谷P3144 [USACO16OPEN]Closing the Farm S 题解 并查集

原文：https://www.cnblogs.com/quanjun/p/12343048.html