글 읽기 - 1707번 틀린이유를 못찾겠습니다...

ejrdnjs96 4년 전 0

30퍼센트까지 돌다가 틀렸습니다 뜨네요 일주일째 답이안나옵니다 도와주세요...

import java.io.*;
import java.util.*;
class graphs{
	int vertex;
	int edge;
	ArrayList<Integer>[] ar;
	int check[];
	
	graphs(int v, int e){
		this.vertex=v;
		this.edge=e;
		ar=(ArrayList<Integer>[])new ArrayList[v+1];
		check=new int[v+1];
		for(int i=1;i<=v;i++) {
			ar[i]=new ArrayList<Integer>();
		}
	}
	// 그래프 생성
	public void init(int n1,int n2) {
		ar[n1].add(n2);
		ar[n2].add(n1);
	}
	//깊이우선 탐색
	public void dfs(int x,int color) {
		if(color==0 || color==2) {
			check[x]=1;
		}
		else if(color==1) {
			check[x]=2;
		}
		for(int i=0;i<ar[x].size();i++) {
			int y=ar[x].get(i);
			if(check[y]==0) {
				dfs(y,check[x]);
			}
		}
	}
	//이분그래프 확인하는 함수
	public boolean Check() {
		for(int i=1;i<=vertex;i++) {
			for(int j=0;j<ar[i].size();j++) {
				int y=ar[i].get(j);
				if(check[i]==check[y]) {
					return false;
				}
			}
		}
		return true;
	}
}
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
		int count= Integer.parseInt(bf.readLine());
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<count;i++) { //test케이스 만큼 반복
			int vertex;
			int edge;
			int start_v=1;
			String line[]=bf.readLine().split(" ");
			vertex=Integer.parseInt(line[0]);
			edge=Integer.parseInt(line[1]);
			graphs gp=new graphs(vertex,edge); //그래프 객체 생성
			
			for(int j=0;j<edge;j++) {
				String lines[]=bf.readLine().split(" ");
				int n1=Integer.parseInt(lines[0]);
				int n2=Integer.parseInt(lines[1]);
				if(j==0) {
					start_v=n1;
				}
				//**여기부터 그래프 초기화하고 탐색후 색깔로 이분그래프 판별하기만하면됨**
				gp.init(n1, n2);
			}
			gp.dfs(start_v, 0);
			boolean result=gp.Check();
			if(result==false) {
				sb.append("NO\n");
			}
			else
				sb.append("YES\n");
		}
		System.out.print(sb);
	}
}

djm03178 4년 전 0

1주일동안 혼자 힘들어하지 마시고, 제발 질문글을 올릴 때 읽으라고 나오는 공지사항에 굵은 글씨에 쓰인 대로 질문 게시판의 다른 질문들을 읽어주세요.

https://www.acmicpc.net/board/view/28396

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

문제

문제

출처

ICPC

1707번 틀린이유를 못찾겠습니다...

ejrdnjs96 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말