[백준] 14567번 : 선수과목 - C++

문제

 

https://www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

---

설명

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

//14567

vector<int> a[1001];
int degree[1001];
int result[1001];
queue<int> q;

int main()
{
    int N,M;
    
    cin >> N >> M;
    
    for(int i = 0;i<M;i++)
    {
        int A,B;
        cin >> A >> B;
        a[A].push_back(B);
        degree[B]++;
    }
    for(int i = 1; i<= N; i++)
    {
        if(degree[i] == 0)
            q.push(i);
        result[i] = 1;
    }
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        for(int i = 0;i<a[x].size();i++)
        {
            int next = a[x][i];
            --degree[next];
            if(degree[next] == 0)
            {
                q.push(next);
                result[next] = max(result[x]+1, result[next]);
            }
        }
    }
    
    for(int i = 1; i<=N; i++)
    {
        cout<<result[i]<< " ";
    }
}

위상정렬 문제이다. 이 문제를 통해서 위상정렬에 대해 처음 공부해 보았다.

위상정렬에서는 사이클이 발생하면 안되고, 시작점이 존재해야 한다.

 

1. 진입차수가 0인 정점들을 큐에 삽입한다.

2. 큐에서 원소를 꺼내면서 연결된 간선들을 제거한다.

3. 간선 제거 이후에 진입차수가 0인 정점들은 큐에 삽입한다.

4. 큐가 빌때까지 2~3과정을 반복한다.

 

 

https://m.blog.naver.com/ndb796/221236874984