[백준] 20119 클레어와 물약

문제

세상에는 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을 넘지 않는다.

출력

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

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

 

하나의 물약을 만드는데 여러개의 레시피가 존재할 수 있습니다.

따라서 물약의 레시피에대해 2차원 배열로 정보를 저장해야합니다.

 

기본적으로 가지고 있는물약이 있고, 그 물약들을 바탕으로 만들 수 있는 물약을 순서대로 만들면 됩니다.

위상정렬 문제입니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;
int N, M, L;
vector<pair<int,int>> recipe[200001]; //n이 들어있는 레시피 <b, index번째 레시피>
int num[200001]; //num[n] n 의 레시피 개수(인덱스 저장용도)
vi n[200001]; //n[n][k] n번째 물약의 k번째 레시피에 필요한 물약의 개수
int have[200001], cnt;
int main() {
	FAST;
	int x, a, b;
	cin >> N >> M;
	REP(i, N)n[i].push_back(0); //0번째 레시피 null
	while (M--) {
		cin >> x;
		vi temp;
		while (x--) {
			cin >> a;
			temp.push_back(a);
		}
		cin >> b;
		num[b]++; //b를 만드는 레시피 인덱스(개수)
		for (int c : temp) {
			recipe[c].push_back({ b,num[b] }); 
            //물약 c가있으면 물약 b의 인덱스 num[b]번째 레시피
		}
		n[b].push_back(temp.size()); //b의 num[b]번째 레시피에 필요한 물약의 개수
	}
	cin >> L;
	queue<int>q;
	while (L--) {
		cin >> x;
		have[x] = 1;
		q.push(x);
		cnt++;
	}
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (auto [nxt, idx] : recipe[cur]) {
			if (have[nxt])continue;
			if (!(--n[nxt][idx])) {
				have[nxt] = 1;
				cnt++;
				q.push(nxt);
			}
		}
	}
	cout << cnt << "\n";
	REP(i, N) {
		if (have[i])cout << i << " ";
	}
}