글 읽기 - 자꾸 60 70퍼이쯤에서 틀려요.. 도와주세요

GGuu 6년 전 0

BFS로 맞게짠거같은데 예제는 돌아갑니다.

여러분들의 힘이 필요해요 ㅠㅠ

// BFS_DFS;
// 0305
import java.util.*;

public class Main {
	static ArrayList<Integer> arr[];
	static int N,M;
	static int check[];
	static int sum[];

	static void bfs(int v,int cnt) {
		Queue<Integer> q = new LinkedList<>();
		check[v] = cnt;
		q.add(v);
		while(!q.isEmpty()) {
			v = q.poll();
			for(int y : arr[v]) {
				if(check[y] == 0) {
					check[y] = cnt;
					q.add(y);
				}
				cnt+=1;
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();

		arr = new ArrayList[N+1];
		check = new int[N+1];
		sum = new int[N+1];
		for(int i = 1 ; i <= N ; i++) {
			arr[i] = new ArrayList<>();
		}

		for(int i = 0 ; i < M ; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			arr[u].add(v);
			arr[v].add(u);
		}
		for(int i = 1 ; i <= N ; i++) {
			bfs(i,1);
			for(int j = 1 ; j <= N ; j++) {
				sum[i] += check[j];
			}
			sum[i]-=1;
			Arrays.fill(check, 0);
		}
		int ans = -1;
		int index = 0;
		for(int i = 1 ; i <= N ; i++) {
			if(ans == -1 || ans >= sum[i]) {
				ans = sum[i];
				index = i;
			}
		}
		System.out.println(index);
	}
}

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

문제

문제

출처

ICPC

자꾸 60 70퍼이쯤에서 틀려요.. 도와주세요

GGuu 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말