BOJ 백준온라인져지 1766 문제집 풀이

ACM CRAFT와 비슷한 문제다.

1. in-degree가 0인거 부터

2. 문제 번호가 낮은거 우선순위

문제 번호가 낮은거 우선순위는 priority_queue로 하면되고,

in-degree는 위상정렬

	#include <cstdio>
	#include <queue>
	#include <vector>
	/**
	* https://www.acmicpc.net/problem/1766
	* BOJ 백준온라인져지 1766 문제집 풀이
	*/
	using namespace std;
	int main () {
	int numberOfVector;
	int numberOfEdge;
	scanf("%d%d", &numberOfVector, &numberOfEdge);
	numberOfVector++;
	numberOfEdge++;
	int *indegree = new int[numberOfVector];
	vector<vector<int> > edges;
	edges.resize(numberOfVector);
	for (int i = 1; i < numberOfVector; i++) {
	indegree[i] = 0;
	}
	for (int i = 1; i < numberOfEdge; i++) {
	int firstSolve;
	int lastSolve;
	scanf("%d%d", &firstSolve, &lastSolve);
	edges[firstSolve].push_back(lastSolve);
	indegree[lastSolve]++;
	}
	priority_queue<int, vector<int>, greater<int> > queue;
	for (int i = 1; i < numberOfVector; i++) {
	if (indegree[i] == 0) queue.push(i);
	}
	while (queue.size()) {
	int here = queue.top();
	queue.pop();
	printf("%d\n", here);
	for (int i = 0, size = edges[here].size(); i < size; i++) {
	int there = edges[here][i];
	indegree[there]--;
	if (indegree[there] == 0) queue.push(there);
	}
	}
	}

view raw BOJ_1766.cpp hosted with ❤ by GitHub