글 읽기 - 반례를 못찾겠네요 ..

b5460881 5년 전 0

bfs로 풀었는데 반례를 찾는거 도와주십쇼 ㅠㅠㅠ

import java.util.*;
public class Main {
	static ArrayList<Integer> a[];
	static int check[];
	static boolean bfs(int start) {
		Queue<Integer> q= new LinkedList<Integer>();
		q.add(start);
		check[start]=1;
		while(!q.isEmpty()) {
			int x=q.remove();
			for(int i:a[x]) {
				if(x==i) {
					return false;
				}
				if(check[i]==0) {
				q.add(i);
				check[i]=3-check[x];
				}
				else if(check[i]!=3-check[x]&&i!=x) {
					return false;
				}
			}
		}
		return true;
		
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		boolean p=true;
		boolean pp=true;
		for(int i=0;i<n;i++) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			a=(ArrayList<Integer>[]) new ArrayList[x+1];
			for(int j=1;j<x+1;j++) {
				a[j]=new ArrayList<Integer>();
			}
			for(int j=0;j<y;j++) {
				int b=sc.nextInt();
				int c=sc.nextInt();
				a[b].add(c);
				a[c].add(b);
			}
			check= new int[x+1];
			for(int j=1;j<=x;j++) {
				if(check[j]==0) {
					if(p==false) {
						break;
					}
					p=bfs(j);
				}
			}
			if(p==true) {
				System.out.println("YES");
			}
			else {
				System.out.println("NO");
			}
			
		}
		

	}

}

djm03178 5년 전 0

2
3 3
1 2
2 3
3 1
2 1
1 2

b5460881 5년 전 0

어휴 감사합니다... 반례찾는법은 하나하나 해보는수밖에없나요???

b5460881 5년 전 0

초기화 문제였군요 ㅠㅠ

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

문제

문제

출처

ICPC

반례를 못찾겠네요 ..

b5460881 5년 전 0

djm03178 5년 전 0

b5460881 5년 전 0

b5460881 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말