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

 

풀이)

이 문제는 위상정렬을 이용하는 문제로, 저의 경우 큐를 이용하여 문제를 해결하였습니다. 

위상 정렬 문제는 처음 풀어봐서 제가 설명드리는 것 보다 문제풀이에 참고한 사이트를 소개해드리겠습니다.

 

https://m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

이분 설명진짜 잘 하십니다..

 

 

코드)

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int n, m;
vector<vector<int>>graph;
vector<int> result;
vector<int> indegree;


void topologysort() {
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (indegree[i] == 0) q.push(i);
	}

	while (not q.empty()) {
		
		int tmp = q.front();
		q.pop();
		result.emplace_back(tmp);

		for (const int a : graph[tmp]) {
			indegree[a]--;
			if (indegree[a] == 0) q.push(a);

		}
	}
}


int main()
{
	cin >> n >> m;
	graph.resize(n+1);
	indegree.assign(n+1, 0);

	while (m--) {
		int u, v;
		cin >> u >> v;

		graph[u].push_back(v);
		indegree[v]++;

	}

	topologysort();

	for (const int n : result) {
		cout << n << ' ';

	}


}