BOJ 15758 - Milking order (이분탐색, 위상정렬)

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

 

<문제설명>

최대 5만개의 법칙 M개가 주어진다. 법칙마다 순서가 주어진다. 예를들어 1 4 3이면 최종 결과에 1 4 3 이 순서대로 나타나야 한다.

 

앞에서부터 최대한 많은 법칙을 사용해서 유효한 n의 permutation을 만들고자 할 때, n의 permutation을 구하라.

 

<풀이>

앞에서부터 법칙 1개 ~ m개를 만족할 때에 대해 가능한지 이분탐색한다.

 

bool pos(int k) 함수에서 앞에서부터 k개의 법칙을 이용해서 위상정렬 가능한지 반환하면 된다.

 

단, 가능한 수열 중 사전 순으로 가장 앞선 수열을 출력해야하므로 위상정렬시 pq를 쓰면 된다.

 

<코드>

int n, m, ind[MAX];
vector<P> odr[50004];
vector<int> topo;
vector<int> adj[MAX];

bool pos(int k) {
	topo.clear();
	for (int i = 1; i <= n; i++) {
		adj[i].clear();
		ind[i] = 0;
	}
	for (int i = 0; i < k; i++) {
		for (int j = 0, u, v; j < odr[i].size(); j++) {
			tie(u, v) = odr[i][j];
			adj[u].push_back(v);
			ind[v]++;
		}
	}

	priority_queue<int, vector<int>, greater<int>> q;
	for (int i = 1; i <= n; i++)
		if (ind[i] == 0) q.push(i);
		

	while (!q.empty()) {
		int u = q.top(); q.pop();
		topo.push_back(u);
		for (int v : adj[u]) 
			if (--ind[v] == 0) 
				q.push(v);
	}

	return topo.size() == n;
}

int main() {
	FAST; cin >> n >> m;
	for (int i = 0,q,u; i < m; i++) {
		cin >> q;
		u = 0;
		for (int j = 0,v; j < q; j++) {
			cin >> v;
			if (u != 0) odr[i].push_back({ u,v });
			u = v;
		}
	}

	int lo = 1, hi = m;
	while (lo < hi) {
		int mid = (lo + hi+1) / 2;
		if (pos(mid))lo = mid;
		else hi = mid - 1;
	}
	pos(lo);
	for (int i : topo) cout << i << " ";
	cout << '\n';
}

 

<생각>