백준 #1766 문제집 : 선행조건이 여러 개인 경우?

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

선행 조건( 보다 쉬운 문제) 이 딱 하나인 경우 트리 선회하면서 해결할 수 있다. 아래 코드로 해결 가능.

근데 이 문제는 선행 조건이 여러 개일 수 있다..!

 

#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

set<int> first;
int find_first[32001];
int v_up[32001];

priority_queue<int> q;
int N, M;

int find(int a) {
	if (find_first[a] == 0) return a;
	int k = find(find_first[a]);
	find_first[a] = k;
	return k;
}

int main(int argc, char argv[]) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		find_first[b] = a;
		v_up[a] = b;
	}
	for (int i = 1; i <= N; i++) {
		first.insert(find(i));
	}
	for (auto i : first) {
		q.push(-i);
	}
	while (!q.empty()) {
		int k = -q.top();
		q.pop();
		cout << k << ' ';

 

근데 선행 조건이 여러 개인 경우는?

내 선행 조건이 몇 개인지를 기억한다.

문제를 하나 풀때마다 그 문제를 선행 조건으로 가지는 문제들의 선행 조건 개수를 1씩 줄인다.

선행 조건 개수가 0이 됐으면 그 문제를 풀 수 있는 문제 큐에 넣는다.

이 큐는 우선순위 큐로 가장 쉬운 문제 (번호가 작은 문제) 부터 pop 한다.