백준 2252

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

2252번: 줄 세우기

위상정렬 (Topology Sort)

업무의 일정을 일어나야 할 순서에 따라 배치 (ex. 대학의 선수과목 구조, 스타크래프트 건물 짓는 순서)

수행과정 (출처: https://ko.wikipedia.org/wiki/위상정렬 )

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음.
2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제
3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다.

필요한 자료구조

1. 벡터: 그래프 저장 (인접 리스트)

2. 배열: 각 노드의 in-degree 저장

3. 큐: in-degree가 0인 노드 저장 (다음에 탐색할 것)

 

012345

 

#include <iostream>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, m;
vector<vector<int> > v;
queue<int> q;
int in[32001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    v.resize(n + 1);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        in[b]++;
    }
 
    // in-degree가 0인 노드 삽입
    rep(i, n) {
        if (in[i] == 0) {
            q.push(i);
            cout << i << ' ';
        }
    }
 
    // queue에 있는 노드와 연결된 간선 제거
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i : v[now]) {
            if (--in[i] == 0) {
                cout << i << ' ';
                q.push(i);
            }
        }
    }
}