[6일차] 그래프1 B - 2252 : 줄 세우기

골드 Ⅲ

 

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

int N, M;
int indegree[32001] = { 0, };
vector<int> adjList[32001];
queue<int> toStart;

int main() {
	scanf("%d%d", &N, &M);
	int A, B;
	while (M--) {
		scanf("%d%d", &A, &B);
		//들어오는 노드 indegree++
		indegree[B]++;
		//인접 리스트에 push
		adjList[A].push_back(B);
	}
	//N개의 노드들 중 indegree가 0인 거 큐에 넣어줌
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) toStart.push(i);
	}
	//위상정렬 ㄱㄱ
	while (toStart.size()) {
		//toStart 비면 끝 -> 조건 while문 안에 씀
		//toStart에서 시작할 노드 뽑기
		int startNode = toStart.front();
		toStart.pop();
		printf("%d ", startNode);
		//startNode 노드와 연결된 노드들 indegree 하나씩 뺴주기
		for (auto i : adjList[startNode]) {
			indegree[i]--;
			//뺐는데 0 됐으면 toStart에 넣어주기
			if (indegree[i] == 0) toStart.push(i);
		}
	}
}

 

위상정렬 문제

-> 여러개의 상위/하위 개념들을 주고 그에 따른 여러가지 순서가 가능할 때 하나의 순서 출력

 

그냥... 강사님 설명 듣고

틀릴줄알고 돌려본건데 왜 맞을까

제대로 완벽하게 이해가 되지 않았을거같은..느낌...

맞나

그리고 뭔가 코너 케이스도.. 안고려해봤어서

괜찮나?