[Algorithm] 위상정렬

Directed Acyclic Graph 방향성이 있고,사이클 없는 그래프

Posted by Wonyong Jang on March 12, 2020 · 3 mins read

위상정렬

스크린샷 2020-03-12 오후 9 06 59 스크린샷 2020-03-12 오후 9 07 16 스크린샷 2020-03-12 오후 9 07 34
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);
                }
            }
        }

백준 관련문제

백준 2252 줄세우기, 1766 문제집, 2623 음악프로그램, 1516 게임 개발, 1005 acm craft, 9470 strahler 순서