글 읽기 - 이렇게 푸는게 아닌가요?

minjea917 2년 전 0

위상정렬 + DFS를 사용했구요

1부터 DFS를 시작해서 rank가 0인 층들은 다시 DFS를 돌려줬습니다.

그 다음 방문하지 않은 층들에 대해 다시 DFS를 돌려주는 식입니다

이 방식이 아닌가요?

import java.io.*;
import java.util.*;

class Main {

    static int N;
    static int[] rank;
    static boolean[] visit;
    static ArrayList<Integer>[] graph;
    static ArrayList<Integer> orders = new ArrayList<>();
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws Exception {
        input();
        solve();
        print();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        rank = new int[N + 1];
        graph = new ArrayList[N + 1];
        visit = new boolean[N + 1];
        for (int i = 1; i <= N; i++)
            graph[i] = new ArrayList<>();

        int e;
        for (int i = 1; i <= N; i++) {
            e = Integer.parseInt(st.nextToken());
            graph[i].add(e);
            rank[e]++;
        }
    }

    private static void solve() {
        dfs(1);
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                orders.add(i);
                dfs(i);
            }
        }
        answer.append(orders.size()).append("\n");
        for(int order : orders)
            answer.append(order).append(" ");
    }

    private static void dfs(int here) {
        visit[here] = true;
        for (int there : graph[here]) {
            if (--rank[there] == 0) {
                orders.add(there);
                dfs(there);
            }
        }
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer.toString());
        bw.flush();
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이렇게 푸는게 아닌가요?

minjea917 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말