[백준1707] 문제를 통해 이분 그래프 이해하기

 

이분그래프란?

위의 그림과 같이 A(검정)/B(회색)로 나눌 수 있는 그래프

A에 포함된 정점끼리 연결된 간선이 없음

B에 포함된 정점끼리 연결된 간선이 없음

A-B 서로를 연결하는 간선만 존재

 

EX. 수강신청 시 학생과 과목을 연결, 소유물 표현 시 사람과 사물을 연결할 때 등 쓰인다

 

-----

이분그래프 관련 문제

 

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

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

public class Main {
	//0은 체크안함, 1/2로 속한 그룹을 체크한다.
    static int[] checked;
    static ArrayList<Integer>[] g;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();

        for (int i = 0; i < k; i++) {
            int v = sc.nextInt();
            int e = sc.nextInt();

            checked = new int[v+1];
            g = new ArrayList[v+1];

            for (int j = 1; j <= v; j++) {
                g[j] = new ArrayList<Integer>();
            }

            for (int j = 0; j < e; j++) {
                int num1 = sc.nextInt();
                int num2 = sc.nextInt();

                g[num1].add(num2);
                g[num2].add(num1);
            }

            boolean result = true;
            for (int j = 1; j <= v; j++) {
                if (checked[j] == 0) {
                    if(!dfs(j, 1)) result = false;
                }
            }

            System.out.println(result?"YES":"NO");


        }
    }

    static boolean dfs(int node, int c) {
        checked[node] = c;
        for (int i = 0; i < g[node].size(); i++) {
            int next = g[node].get(i);
            if(checked[next] == 0){
                if(dfs(next, 3 - c) == false){
                    return false;
                }
            } else if (checked[node] == checked[next]) {
                return false;
            }
        }
        return true;
    }
}