백준 2252 / CPP / 위상 정렬

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

이 문제는 위상정렬 알고리즘을 사용하는 문제이다
https://terms.naver.com/entry.naver?docId=3579618&cid=59086&categoryId=59093

위상 정렬 알고리즘

해당 게시물을 참조하면 이해가 쉬울 것이다
즉 순서에 맞춰서 나열 하면 되는게 위상 정렬 이다

이 문제에서는 어떠한 노드 가 나로 올수 있는 점입차수 라는것을 들고 있어야 한다 점입차수가 0이면 먼저 뽑아도 무방한 노드라고 보면 된다 즉 우리는 이문제를 풀때 점입차수를 비교해가며 큐에 넣어서 pop 하면 되는 문제이다

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

int main() {
	int n, m;
	cin >> n >> m;
	int inCount[100001] = { 0, };
	vector<vector<int>> v(n + 1);
	for (int i = 0; i < m; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		v[tmp1].push_back(tmp2);
		inCount[tmp2]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (inCount[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		cout << q.front() << " ";
		int idx = q.front();
		for (int i = 0; i < v[idx].size(); i++) {
			inCount[v[idx][i]] -= 1;
			if (inCount[v[idx][i]]<=0)
				q.push(v[idx][i]);
		}
		q.pop();
	}
}

일단 전체 코드는 이렇게 된다
입력 받을 때 어떠한 노드를 입력 받고 이노드가 갈수 있는 노드도 Vector에 넣어 놓느다 그후  연결 된 노드의 점입  차수를 1증가 시킨다  이렇게 입력 을 받은 후
우리는 해당 vector를 순회하면 서 일단 점입차수가 0인걸 queue에다가 넣는다
그후 while문으로 큐를 순회하면서 점입차수가 0인 걸 팝해주면 나와 연결된 노드들의 점입 차수를 1감소시켜준다 그렇게 점입차수가 0인 노드들을 지속적으로 queue에 넣었다 팝해주면 해당 문제는 풀린다