[백준 c++] 1766 문제집

우선순위 큐를 이용한 위상정렬 문제다.
아래는 먼저 indgree를 이용한 위상정렬에 대한 내용 정리

💡 indgree를 이용한 위상정렬

위상정렬이란?
⇒ 사이클이 없는 방향 그래프 (DAG)에서 방향성을 거스르지 않게 정점들을 나열하는 알고리즘

indgree란?
⇒ 자신에게 들어오는 방향의 간선의 수

알고리즘 원리
1. 진입차수가 0인 정점(A) 큐에 삽입
2. A 출력
3. A와 연결된 정점(B)들의 진입차수를 1씩 감소시킨다.
4. B의 진입차수가 0이면 큐에 삽입

필요한 것
⇒ 큐 , 연결리스트 vector node[32001] , indgree[32001]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAX 987654321
int n, m, a, b;
vector<int> node[32001];
int indgree[32001];
priority_queue<int, vector<int>, greater<int>> q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;

    while (m--)
    {
        cin >> a >> b;
        node[a].push_back(b);
        indgree[b]++;
    }

    for (int i = 1; i <= n; i++)
    {
        if (indgree[i] == 0)
            q.push(i);
    }

    while (!q.empty())
    {
        int f = q.top();
        q.pop();
        cout << f << " ";
        for (int i : node[f])
        {
            if (--indgree[i] == 0)
                q.push(i);
        }
    }
}