[BOJ-2252]줄세우기

위상정렬을 사용하는 문제.

1. 모든 입력에 대한 차수를 매기고, 연결된 간선을 구성한다.

2. (1) 입력이 끝난 후, 차수가 0인 정점을 모두 큐에 넣는다.

3. 큐 비어 있을 때 까지

 3-0. 큐 에서 뺀 값을 출력한다.

 3-1. 큐에서 빼며 연결된 간선을 처리한다. 이때 차수는 THERE -1 이다. 

 3-2. THERE 의 차수가 0 이라면 큐에 넣는다.

3을 반복하고 비어있다면 프로그램을 종료한다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
 
typedef vector<int> VI;
 
VI deg;
VI edge[33333];
 
int main(){
    int stud, m;
    scanf("%d%d", &stud, &m);
    deg = VI(stud+1, 0);
    for(int i = 0 ; i < m ; i++){
        int u,v;
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        deg[v]++;
    }
    
    queue<int> Q;
    for(int stu = 1 ; stu <= stud ; stu++)
        if(deg[stu] == 0) Q.push(stu);
 
    while(!Q.empty()){
        int here = Q.front(); Q.pop();
        printf("%d ",here);
        
        for(auto iter = edge[here].begin() ; iter != edge[here].end() ; iter++){
            int there = *iter;
            deg[there]--;
            if(deg[there] == 0)    Q.push(there);
        }
    }
    return 0;
}