글 읽기 - 시간 초과 해결 방법을 모르겠습니다.

ljs921026 5년 전 0

시간을 어떻게 더 줄여야 할지 몰라서 질문 남깁니다.

dfs 안에서 dp를 사용해보려고 했는데

사이클이 생길 경우에는 어떻게 처리해야할지 몰라 질문 남깁니다.

import java.util.*;

public class Main {
	static ArrayList<ArrayList<Integer>> Graph;
	static boolean[] check;
	static int[] d;
	static int number;
	
	public static void dfs( int x) {
		if(check[x])
			return;
		check[x]=true;
		number++;
		for(int y:Graph.get(x)) {
			if(check[y]==false)
				dfs(y);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();//정점 갯수
		int M=sc.nextInt();//간선 갯수
		
		Graph=new ArrayList<ArrayList<Integer>>();
		for(int i=0;i<=N;i++) {
			Graph.add(new ArrayList<Integer>());
		}
		
		for(int i=0;i<M;i++) {
			int end=sc.nextInt();
			int start=sc.nextInt();
			
			Graph.get(start).add(end);
		}
		
		d=new int[N+1];
		for(int i=1;i<=N;i++) {
			check=new boolean[N+1];
			number=0;
			dfs(i);
			d[i]=number;
		}
		
		int max=d[1];
		for(int i=1;i<=N;i++) {
			if(max<d[i])
				max=d[i];
		}
		for(int i=1;i<=N;i++) {
			if(d[i]==max)
				System.out.print(i+" ");
		}
	}
}

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

문제

문제

출처

ICPC

시간 초과 해결 방법을 모르겠습니다.

ljs921026 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말