위상정렬

2252 줄 세우기 : https://www.acmicpc.net/problem/2252

위상정렬

: DAG(비 순환 방향 그래프)에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것

- 각 정점을 우선순위에 따라 배치함

- 일반적으로 위상정렬의 결과는 유일하지 않음

- 위상정렬 수행 과정

1) 자기 자신을 가리키는 간선이 없는 정점을 찾음(in-degree == 0)

2) 찾은 정점을 출력하고, 출력한 정점과 그 정점에서 출발하는 간선을 삭제

3) 아직 그래프에 정점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료

    //초기 degree 값이 0인 것 큐에 넣음

    for(int i=1; i<=n; i++){

        if(degree[i] == 0){

            q.push(i);

        }

    }

    

    // 위상정렬 시작

    while(!q.empty()){

        int node = q.front(); q.pop();

        printf("%d ", node);

        for(int i=0; i<adj[node].size(); i++){

            int nnode = adj[node][i];

            degree[nnode]--;

            if(degree[nnode] == 0) q.push(nnode);

        }

    }