[BOJ] 12004 - Closing the Farm(Silver)

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

BOJ - Closing the Farm

문제 유형: bfs/dfs, 그래프

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 512MB

 

문제

Farmer John and his cows are planning to leave town for a long vacation, and so FJ wants to temporarily close down his farm to save money in the meantime.

The farm consists of N barns connected with M bidirectional paths between some pairs of barns (1 <= N, M <= 3000). To shut the farm down, FJ plans to close one barn at a time. When a barn closes, all paths adjacent to that barn also close, and can no longer be used.

FJ is interested in knowing at each point in time (initially, and after each closing) whether his farm is "fully connected" -- meaning that it is possible to travel from any open barn to any other open barn along an appropriate series of paths. Since FJ's farm is initially in somewhat in a state of disrepair, it may not even start out fully connected.

 

농장은 N개의 외양간과 M개의 양방향길로 이어져있다.

외양간을 폐쇄하면, 해당 외양간과 그에 부속된 길을 이용할 수 없다.

순차적으로 임의의 외양간을 닫으면서, 그 과정에서 농장 내부가 완전히 연결되어있는 지 궁금해졌다.

 

입력

The first line of input contains N and M. The next M lines each describe a path in terms of the pair of barns it connects (barns are conveniently numbered 1 ... N. The final N lines give a permutation of 1 ... N describing the order in which the barns will be closed.

 

첫째 줄에 N과 M이 주어진다.

이후 M개의 줄에는 외양간의 연결 정보가 주어진다.

마지막 N개의 줄에는 1...N의 순열이 있다.

 

출력

The output consists of N lines, each containing "YES" or "NO". The first line indicates whether the initial farm is fully connected, and line i+1 indicates whether the farm is fully connected after the ith closing.

 

첫 번째 줄에 농장의 처음 상태를 출력한다.

i+1번째 줄에는 i번째의 외양간 폐쇄 이후로 어떤지를 출력한다. (1 <= i < N)

모두 연결되어있다면 YES, 아니라면 NO를 출력한다.

 

풀이

bfs함수를 정의한다.

bfs에서는 금지된 외양간을 가지 못하도록 구현하고, 최종적으로 금지된 외양간 외에 방문 못한 외양간이 있으면 하나의 연결 컴포넌트인것으로 간주하고, true를, 아니라면 두 개 이상의 연결컴포넌트로 나뉘어져 있는 것으로 간주하여 false로 반환한다.

 

(bfs() -> 외양간 폐쇄)를 N번 반복하면 된다.

bfs는 금지되지 않은 임의의 점에서 시작하면 된다.

아래 코드에서는 항상 남아있는 외양간 중 가장 작은 번호부터 시작한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, m;

bool bfs(int start, vector<vector<int>>& adj, vector<bool>& banned) {
    vector<bool> visited(n + 1);
    queue<int> q;
    q.emplace(start);
    visited[start] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (const auto& next : adj[curr]) {
            if (banned[next]) continue;
            if (!visited[next]) {
                q.emplace(next);
                visited[next] = true;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!banned[i] && !visited[i]) return false;
    }

    return true;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    vector<int> del(n);
    for (auto& i : del) cin >> i;

    vector<bool> banned(n + 1);
    int start = 1;
    for (int i = 0; i < n; i++) {
        if (bfs(start, adj, banned)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }

        banned[del[i]] = true;
        if (del[i] == start) {
            while (banned[start]) {
                start++;
            }
        }
    }

    return 0;
}