글 읽기 - 시간초과 도와주세요..

wwdbsh 5년 전 0

14%에서 시간초과 못넘어가네요ㅠㅠ 많이 부족하지만 잘못된 부분 짚어 주시면 감사하겠습니다!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.LinkedList;

public class Main
{
	private static LinkedList<Integer>[] adj;
	private static boolean[] chk;
	private static int[] color;
	private static String ans = "YES";
	private static int v, e;

	public static void main(String[] args) throws IOException
	{
		StringTokenizer st;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		while(T-- > 0)
		{
			st = new StringTokenizer(br.readLine());
			v = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			adj = new LinkedList[v+1];
			for(int i = 1; i <= v; i++) adj[i] = new LinkedList<Integer>();
			for(int i = 0; i < e; i++)
			{
				st = new StringTokenizer(br.readLine());
				int v1 = Integer.parseInt(st.nextToken());
				int v2 = Integer.parseInt(st.nextToken());
				adj[v1].add(v2);
				adj[v2].add(v1);
			}
			for(int i = 1; i <= v; i++)
			{
				chk = new boolean[v+1];
				color = new int[v+1];
				chk[i] = true;
				color[i] = 1;
				dfs(i, 1);
			}
			System.out.println(ans);
		}
		br.close();
	}

	private static void dfs(int root, int c)
	{
		if(c == v) return ;
		for(int n : adj[root])
		{
			if(!chk[n])
			{
				color[n] = (color[root] == 1) ? 0 : 1;
				chk[n] = true;
				dfs(n, c + 1);
			}
			else
			{
				if(color[root] == color[n])
				{
					ans = "NO";
					return ;
				}
			}
		}
	}
}

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

문제

문제

출처

ICPC

시간초과 도와주세요..

wwdbsh 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말