백준 1707 이분 그래프 JAVA

 

1707번: 이분 그래프

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	static int n,m;
	static List[] check;
	static int checked[];
	
	//백준 1707번
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t=sc.nextInt();
		
		//테스트 케이스가 0일 될때까지
		while(t-->0) {
			n= sc.nextInt(); //노드갯수
			m= sc.nextInt(); //간선갯수
			
			//배열리스트 쓰는 이유 : 배열을 쓰면 시간초과로 나옴
			check =new ArrayList[n+1];
			//노드 갯수만큼 리스트에 배열리스트 생성
			for(int i=1; i<=n; i++) {
				check[i] = new ArrayList();
			}
			
			//방문 여부 확인
			//0:방문 안함 / 1: 방문한 x소속  / 2:방문한 y소속
			checked = new int[n+1];
			
			//좌표 받아서 배열리스트에 집어넣음
			for(int k=0; k<m; k++) {
				int x=sc.nextInt();
				int y=sc.nextInt();
				
				check[x].add(y);
				check[y].add(x);
			}
			
			for(int i=1; i<=n; i++) {
				if(checked[i]==0) { // 정점 i를 방문하지 않은 상태라면
					dfs(i, 1);
				}
			}
			
			if(isPossible()) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
		}
	}
	
	private static boolean isPossible() {
		for(int i=1; i<=n; i++) {
			for(int k=0; k<check[i].size(); k++) {
				if(checked[i]==checked[(int)check[i].get(k)]) {
					return false;
				}
			}
		}
		return true;
	}
	
	private static void dfs(int node, int c) {
		checked[node] =c;
		
		for(int i=0; i<check[node].size(); i++) {
			int next=(int)check[node].get(i); //지금 선택된 노드에 연결된 노드 값을 가져와서 next에 집어넣음
			if(checked[next]==0) { //연결된 노드 값의 checked가 0이면 들리지 않았다는 것 >> 지금 선택된 노드와 연결되었으니 다른 숫자주기 위해서 3-c로 만들어줌
				dfs(next,3-c);
			}
		}
	}
}