[1766] 문제집

Worldi·2021년 12월 2일
0

알고리즘

목록 보기
26/59
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> v[32001];
int indegree[32001];
priority_queue<int, vector<int>, greater<int>> pq;
void bfs()
{

    while (!pq.empty())
    {
        int next = pq.top();
        cout << next << " ";
        pq.pop();
        for (int y : v[next])
        {
            int nextnode = y;
            indegree[nextnode] -= 1;
            if (indegree[nextnode] == 0)
            {

                pq.push(nextnode);
            }
        }
    }
}
int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int src, dest;
        cin >> src >> dest;
        v[src].push_back(dest);
        indegree[dest]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (indegree[i] == 0)
        {
            pq.push(i);
            //  cout << i << "\n";
        }
    }
    bfs();
    return 0;
}

bfs 를 활용한 위상 정렬 알고리즘이다.
여기서 주의 해야할 점은 최소 힙을 썼다는 것인데, 문제의 조건에 의하면 가능하면 쉬운 문제 부터 풀어야 한다라는 것이 있으므로, 가장 작은 수부터 큐에서 pop을 하여야 한다.

profile
https://worldi.tistory.com/ 로 블로그 이전합니다.

0개의 댓글