글 읽기 - 1766번 문제 dfs로는 풀 수 없나요?? ㅠㅠㅠㅠ 고수님들 도와주세요 ㅠㅠ

ddr04014 6년 전 0

처음에 dfs로 풀다가 계속 답이 안나와서 priorityQueue를 써서 푸니까 풀리긴 풀리더라고요. 근데 dfs로 못푼게 좀 찝찝해서 이렇게 질문 올립니다. dfs로는 어떻게 풀 수 있을까요?

import java.util.*;

public class Main {
	static int N;
	static LinkedList<Integer>[] graph;
	static int[] getEdge;
	static boolean[] visited;

	static ArrayList<Integer> result;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		int M = sc.nextInt();
		int from, to;
		graph = new LinkedList[N+1];
		getEdge = new int[N+1];
		visited = new boolean[N+1];

		result = new ArrayList<Integer>();
		for(int i = 1; i < N+1; i++){
			graph[i] = new LinkedList<Integer>();
		}
		for(int i = 0 ; i < M; i++){
			from = sc.nextInt();
			to = sc.nextInt();
			graph[from].add(to);
			getEdge[to]++;
		}
		topologicalSort();

		for(int i = result.size()-1; i >= 0; i--){
			System.out.print(result.get(i) + " ");
		}
		
	}
	
	
	public static void topologicalSort(){
		for(int i = N; i >=1; i--){
			if(!visited[i]){
				dfs(i);
			}
		}
	}
	public static void dfs(int n){
		visited[n] = true;
		for(int i : graph[n]){
			if(!visited[i]){
				dfs(i);
			}
		}
		result.add(n);
	}
}
	

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

문제

문제

출처

ICPC

1766번 문제 dfs로는 풀 수 없나요?? ㅠㅠㅠㅠ 고수님들 도와주세요 ㅠㅠ

ddr04014 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말