[백준 2252번 / C++] 줄 세우기 (위상 정렬)

위상 정렬 알고리즘

---

위상 정렬 알고리즘을 활용해서 푸는 문제이다. 

위의 링크에서 설명이 잘되어 있으니 해당 알고리즘을 모를 경우 참조하는 것을 권한다. 

 

#접근방법 

1. a정점에서 b정점으로 가는 경로를 이차원 벡터에 v[a].push_back(b) 로 저장을 한다. 
2. b 정점의 진입차수를 증가 시켜준다. ( indegree[b]가 2 라면 앞에 두명이 서있어야한다.)
3. 진입차수가 0인 것부터 차례대로 출력해준다. (queue 활용) 
4. 진입차수가 0인 a정점에서 연결되어있는 b정점이 존재한다면 b정점의 진입차수를 하나 감소시켜주며 감소한 값이 0이 된다면 queue에 넣어준다.  

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
int main() {
	int n, m; 
	cin >> n >> m; 
	vector <vector<int>> v(n + 1);
	int indegree[100001];
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b; 
		v[a].push_back(b); 
		indegree[b]++;
	}
	queue <int> q; 
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0)q.push(i);
	}
	while (!q.empty()) {
		cout << q.front()<<" "; 
		int idx = q.front(); 
		for (int i = 0; i < v[idx].size(); i++) {
			if (!--indegree[v[idx][i]])q.push(v[idx][i]);
		}		
		q.pop(); 
	}	
}

 

2252번: 줄 세우기