글 읽기 - 이분그래프 시간초과 문의드립니다 ㅠㅠ

amabile29 7년 전 0

왜이렇게 시간초과가 나는 것일까요? 문의드립니다

ㅠㅠ도와주세요...

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static boolean check(int x, int color[], int V, boolean map[][]){
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(x);
		color[x]=1;
		
		while(!q.isEmpty()){
			int now = q.poll();
			for(int i=1 ;i<=V; i++){
				if(map[now][i]){//연결
					if(color[i]==0){
						color[i] = -color[now];
						q.add(i);
					}else{
						if(color[i]==color[now]){
							return false;
						}
					}
				}
			}
		}
		
		return true;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();//2<= <=5
		for(int Test_Case=0; Test_Case<K; Test_Case++){
			boolean map[][];
			int color[];
			
			int V = sc.nextInt(); //정점 개수 1~N
			int E = sc.nextInt(); //간선 개수
			map = new boolean[V+1][V+1];
			color = new int[V+1];
			int x=0;
			for(int j=0; j<E; j++){
				x = sc.nextInt();
				int y = sc.nextInt();
				map[x][y] = true;//연결
				map[y][x] = true;
			}//input
			boolean result;
			result = check(x, color, V, map); //연결true, 비연결false
			
			for(int i=1; result && i<=V; i++)
				if(color[i]==0)
					result = check(i, color, V, map);
						
			if(result)
				System.out.println("YES");
			else
				System.out.println("NO");
			
		}
	}

}

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

문제

문제

출처

ICPC

이분그래프 시간초과 문의드립니다 ㅠㅠ

amabile29 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말