12012번: Closing the Farm (Gold)

https://www.acmicpc.net/problem/12012


$O(n+m)$

쿼리를 반대로 봐서 해당 곳간을 열렸다고 표시하고 인접한 곳간들이 속한 집합들을 모두 합친다.
집합이 1개이면 YES 아니면 NO

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 2e5;
int n, m, ck[MXN + 1], a[MXN + 1], p[MXN + 1], r[MXN + 1], c;
vector<int> adj[MXN + 1];
int f(int h) { return h^p[h] ? p[h] = f(p[h]) : h; }
int main() {
        scanf("%d%d", &n, &m);
        for (int i = 0, x, y; i < m; i++) {
                scanf("%d%d", &x, &y);
                adj[x].push_back(y);
                adj[y].push_back(x);
        }
        for (int i = 1; i <= n; i++) scanf("%d", a + i), p[i] = i;
        for (int i = n; i; i--) {
                c++;
                for (auto it : adj[a[i]]) if (ck[it] && f(a[i]) ^ f(it)) {
                        p[f(it)] = f(a[i]);
                        c--;
                }
                ck[a[i]] = 1;
                r[i] = c == 1;
        }
        for (int i = 1; i <= n; i++) puts(r[i] ? "YES" : "NO");
        return 0;
}