[BOJ] 20119 - 클레어와 물약

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

BOJ - 클레어와 물약

문제 유형: DAG, 그래프, 위상 정렬

문제 난이도: Gold II

시간 제한: 1초

메모리 제한: 256MB

 

문제

세상에는 N종류의 물약이 있고 클레어는 M개의 레시피를 알고있다.

레시피는 (x1, x2, ..., xk) → r 형태로 표현할 수 있고 x1번, x2번 ..., xk번 물약을 모두 섞어서 r번 물약을 만들 수 있다는 뜻이다.

현재 클레어에게는 y1번, y2번, ..., yL번 물약만 있다. 만들 수 있는 물약들을 전부 알아내주자.

클레어가 가지고 있는 각 종류의 물약의 양은 무한대라고 가정하자.

 

입력

첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다.

다음 M개의 줄에는 각각의 줄마다 레시피의 정보 ki, xi1, xi2, ..., xiki, ri (1 ≤ ki < N, 1 ≤ xij, ri ≤ N, xij ≠ ri) 가 주어지며 이는 (xi1, xi2, ..., xiki) → ri 형태의 레시피를 의미한다.

M+2 번째 줄에는 현재 클레어가 가지고 있는 물약 종류의 수 L (1 ≤ L < N) 이 주어진다.

M+3 번째 줄에는 y1, y2, ..., yL (1 ≤ yi ≤ N) 이 주어진다.

모든 ki의 합은 400,000을 넘지 않는다.

 

출력

첫 번째 줄에 클레어가 만들 수 있는 물약의 개수를 출력한다.

두 번째 줄에는 만들 수 있는 물약의 번호를 오름차순으로 출력한다.

 

풀이

인접 리스트를 구성하고, 또 추가로, vector<vector<set<int>>>꼴의 자료구조인 recipes를 이용해서 레시피[i] = {필요한 재료 묶음들}을 통해서 i번째 물약에 대한 여러 레시피를 구성했다.

 

현재 가지고 있는 물약들부터 큐에 넣고 위상정렬을 시작해서, 

다음 요소들에 대해 레시피[다음물약] 에서의 set들에서 현재 물약을 제거한다. 만약 빈 set이 하나라도 나오면, 큐에 넣고 방문처리해준다.

 

이렇게 visited에서 1~n중에서 방문한 노드들만 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

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

    cin >> n >> m;

    vector<vector<int>> adj(n + 1);
    vector<vector<set<int>>> recipes(n + 1);

    for (int i = 0; i < m; i++) {
        int k;
        cin >> k;
        set<int> s;
        for (int j = 0; j < k; j++) {
            int x;
            cin >> x;
            s.insert(x);
        }
        int dst;
        cin >> dst;
        for (const auto &src : s) {
            adj[src].emplace_back(dst);
        }
        recipes[dst].emplace_back(s);
    }

    int startSize;
    cin >> startSize;
    vector<bool> visited(n + 1, false);
    queue<int> q;
    for (int i = 0; i < startSize; i++) {
        int x;
        cin >> x;
        q.emplace(x);
        visited[x] = true;
    }

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

        for (const auto &next : adj[curr]) {
            if (visited[next]) continue;
            for (auto &s : recipes[next]) {
                s.erase(curr);
                if (s.empty()) {
                    visited[next] = true;
                    q.emplace(next);
                    break;
                }
            }
        }
    }

    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (visited[i]) ans.emplace_back(i);
    }

    cout << ans.size() << "\n";
    for (const auto &elem : ans) cout << elem << " ";
    cout << "\n";

    return 0;
}