링크

이분 그래프-1707

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int check[];
	public static boolean visited[];
	public static ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
	public static boolean flag=true;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		ArrayList<String> arr=new ArrayList<String>();
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int k=Integer.parseInt(br.readLine());
		
		for(int i=0; i<k; i++)
		{
			StringTokenizer st=new StringTokenizer(br.readLine());
			int v=Integer.parseInt(st.nextToken()); //그래프 정점 개수
			int e=Integer.parseInt(st.nextToken()); //간선의 개수
			check=new int[v+1];
			visited=new boolean[v+1];
			
			Arrays.fill(check, -1);
				
			for(int j=0; j<=v; j++) //그래프 정점
				list.add(new ArrayList<Integer>());
			
			for(int n=0; n<e; n++) //간선의 갯수
			{
				StringTokenizer st1=new StringTokenizer(br.readLine());
				int num1=Integer.parseInt(st1.nextToken());
				int num2=Integer.parseInt(st1.nextToken());
				list.get(num1).add(num2);
				list.get(num2).add(num1);
			}
			
			for(int z=1; z<=v; z++) //분할되지 않은 그래프가 존재할수도 있기 때문
			{
				if(!visited[z])
					DFS(z, 0);
				if(flag==false)
					break;
			}
			
			if(flag==false)
				arr.add("NO");
			else
				arr.add("YES");
			
			flag=true;
			list.clear();
		}
		
		for(int i=0; i<arr.size(); i++)
			System.out.println(arr.get(i));
		
	}
	
	
	public static void DFS(int x, int color)
	{
		visited[x]=true;
		check[x]=color;
		
		for(int i=0; i<list.get(x).size(); i++)
		{
			int num=list.get(x).get(i);
			
			if(!visited[num])
				DFS(num, (color+1)%2);
			else
			{
				if(check[num]==check[x])
				{
					flag=false;
					return;
				}
			}
		}
	}
}