12004번: Closing the Farm (Silver)

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


$O(n(n+m))$

문제 그대로 구현.
매번 dfs 탐색을 해서 해당 곳간으로 부터 갈 수 있는 곳의 개수와 열린 곳간의 개수가 같은지 보고 해당 곳간을 닫는다.

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int n, m, ck[3001], cls[3001];
vector<int> adj[3001];
int f(int h) {
        if (cls[h] || ck[h]) return 0;
        ck[h] = 1;
        int s = 1;
        for (auto it : adj[h]) s += f(it);
        return s;
}
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 = n, x; i; i--) {
                memset(ck, 0, sizeof(ck));
                scanf("%d", &x);
                puts(f(x) == i ? "YES" : "NO");
                cls[x] = 1;
        }
        return 0;
}