[C++] 백준 BOJ 2252 줄 세우기

문제링크 : https://boj.kr/2252

위상정렬을 이용한 문제로 자신을 가리키는 간선이 없는 경우 즉, indegree가 0인 정점을 찾는다.

자신을 가리키는 간선(indegree)가 1개 이상 있다는 의미는 자신의 노드가 뒷쪽에 나와야 한다는 것을 의미한다.

찾은 정점을 큐에 넣고 간선을 삭제한다.

반복

자료 입력 순서가 중요하면 우선순위 큐를 사용하면 된다.

// BOJ 2252 줄 세우기
// DAG (Directed Acyclic Graph)
// 순환을 가지지 않는 방향그래프
// 위상정렬 (Toplogical Sort)
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
 
    int num, cnt;
    cin >> num >> cnt;
    vector<vector<int> > arr(num + 1, vector<int>());
    vector<int> degree(num + 1, 0);
    queue<int> qq;
 
    int a, b;
    for (int i = 0; i < cnt; i++) {
        cin >> a >> b;
        arr[a].push_back(b);
        degree[b]++;
    }
    for (int i = 1; i <= num; i++)
        if (degree[i] == 0)
            qq.push(i);
 
    while (!qq.empty()) {
        int node = qq.front();
        qq.pop();
        cout << node << " ";
        for (int i = 0; i < arr[node].size(); i++) {
            int nn = arr[node][i];
            degree[nn]--;
            if (degree[nn] == 0) qq.push(nn);
        }
    }
    return 0;
}