[Algorithm] 위상정렬

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
        int dx = 0, dy = 0;
        for(int i=1; i<= M; i++) {
            st = new StringTokenizer(br.readLine());
            dx = Integer.parseInt(st.nextToken());
            dy = Integer.parseInt(st.nextToken());
            adj[dx].add(dy);
            indegree[dy]++; // 선행되어야할 노드 갯수 세기
        }

        for(int i=1; i<= N; i++) { // ingegree == 0 은 선행되어야 할 노드
            if(indegree[i] == 0) que.add(i); // 전부 처리되었으니 진행 가능 !
        }

        int flag = 0; // flag == N 이면 위상정렬 완료
                      // flag > N 사이클 존재 !
                      // flag < N 위상정렬 불가능
        while(!que.isEmpty()) {

            int cur = que.poll();
            flag++;
            bw.write(cur + " ");

            for(int next : adj[cur]) {
                indegree[next]--;
                if(indegree[next] == 0) {
                    que.add(next);
                }
            }
        }