BOJ 2252: 줄 세우기

#BOJ 2252: 줄 세우기

#풀이

위상정렬로 해결할 수 있는 문제이다.

 

입력 a b

a가 b보다 먼저 나와야 한다는 뜻이므로 

인접리스트에 저장할 때 a->b 로 생각하고 저장해야 한다.

 

또한 b 의 indegree 값도 1 증가 해줘야 한다.

 

위상 정렬은 쉽게 말해서 자신에게 들어오는 간선이 없는 정점을 찾아가면 된다.

 

맨 처음에 자신에게 들어오는 간선이 없는 정점을 찾았으면 그 정점을 그래프에서 지우면 된다.

 

지우는 것을 어렵게 생각하지 말고 어차피 indegree를 통해서 판단하므로

 

a 에서 나가는 간선을 저장하는 인접리스트에 있는 정점들의 indegree를 1 감소 시키면 된다.

 

#코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int>adj[32001];
int deg[32001];
int n, m;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		deg[b]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (deg[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		int a = q.front(); q.pop();
		for (auto b : adj[a]) {
			deg[b]--;
			if (deg[b] == 0)
				q.push(b);
		}
		cout << a << ' ';
	}
	cout << '\n';

	return 0;
}