백준 1766번: 문제집 (C++)

문제 링크 : www.acmicpc.net/problem/1766

 

 

위상정렬 문제이다.

 

위상정렬 알고리즘  :  wlshddlek.tistory.com/39?category=887828

 

 

<전체적인 알고리즘>

위상정렬을 이용해야 한다. 위상정렬을 이용할 때 일반 큐가 아니라 우선순위 큐를 사용하면 

실시간으로 탐색할 수 있는 것 중에 작은거 부터 탐색할 수 있다.

 

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include<iostream> #include<vector> #include<queue>   using namespace std;   int n, m; vector<int> a[32002]; int indegree[32002];   void topology()  //우선순위큐를 이용한 위상 정렬 {     priority_queue<int> pq;  //실시간으로 선택할 수 있는 것 중 가장 작은거 선택 위함     for (int i = 1; i <= n; i++)     {         if (indegree[i] == 0)pq.push(-i);  //우선순위 큐는 내림차순 정렬이라서 -붙임     }       while (!pq.empty())     {         int node = -pq.top();         pq.pop();           cout << node << " ";           for (int i = 0; i < a[node].size(); i++)         {             int next = a[node][i];             indegree[next]--;             if (indegree[next] == 0)pq.push(-next);         }     } }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);       cin >> n >> m;     for (int i = 0; i < m; i++)     {         int n1, n2;         cin >> n1 >> n2;         a[n1].push_back(n2);         indegree[n2]++;     }       topology();       return 0; }

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.