최장경로 [SWEA 2814][Java]

[광고 누르면 오늘의 행운 상승!!]

그래프 기본 문제.

DFS로 간선의 최장경로를 찾아내는 문제.

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

public class 최장경로 {
	public static boolean visit[];
	public static Queue<int[]> q;
	public static int N,M;
	public static int map[][];
	public static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		
		int T= sc.nextInt();
		
		for (int tc = 1; tc <= T; tc++) {
			max = Integer.MIN_VALUE;
			N = sc.nextInt();
			M = sc.nextInt();
			
			map = new int[N][N];
			
			for (int i = 0; i < M; i++) {
				int Fn = sc.nextInt()-1;
				int Sn = sc.nextInt()-1;
				
				map[Fn][Sn] = map[Sn][Fn] = 1;
			}
			for (int i = 0; i < N; i++) {
				visit = new boolean[N];
				dfs(i,1);
			}
		
			if(max == Integer.MIN_VALUE)System.out.println("#" + tc + " " + 1);
			else System.out.println("#" + tc + " " +(max));
		}
		
	}
	public static void dfs(int node, int cnt) {
		visit[node] = true;
		
		for (int i = 0; i < N; i++) {
			if(node == i) continue;
			if(map[node][i] == 1 && !visit[i]) {
				
				dfs(i, cnt+1);
				visit[i] = false;
			}
		}
		max = Math.max(cnt, max);
	}

}