글 읽기 - 다음과 같이 DFS로 풀었을때 나올 수 있는 반례가 뭐가 있을까요?

cnc1970kr 2년 전 2

위상정렬을 배우기전 DFS로 작성한 코드인데 여전히 반례를 찾지 못하겠습니다. 다음과 같이 풀었을때 나올 수 있는 반례가 뭐가 있을까요?

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

//1766
public class Main {

    static boolean[] visit;
    static ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
    static StringBuffer sb = new StringBuffer();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        
        // N, M 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        
        //배열 초기화
        visit = new boolean[N + 1];
        for (int i = 0; i < N + 1; i++) arr.add(new ArrayList<Integer>());

        
        //A > B 관계 설정
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int better = Integer.parseInt(st.nextToken());
            int stand = Integer.parseInt(st.nextToken());

            arr.get(stand).add(better);
        }

        for(int i = 1; i < N + 1; i++) DFS(i);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static void DFS(int start){

        if(visit[start]) return;
        
        //정렬
        if(arr.get(start).size() != 0) Collections.sort(arr.get(start));
        
        //탐색
        for(int i = 0; i < arr.get(start).size(); i++){
            DFS(arr.get(start).get(i));
        }
        sb.append(start + " ");
        visit[start] = true;
    }

}

djs100201 2년 전 8

6 7

5 6

5 2

2 4

4 3

2 1

6 1

1 3

ans: 5 2 4 6 1 3

output 5 2 6 1 4 3

cnc1970kr 2년 전 0

감사합니다.

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

문제

문제

출처

ICPC

다음과 같이 DFS로 풀었을때 나올 수 있는 반례가 뭐가 있을까요?

cnc1970kr 2년 전 2

djs100201 2년 전 8

cnc1970kr 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말