이분 그래프

📍 문제 설명

 

💡 접근

둘로 분할해야 하므로 전체 영역에 대해서 탐색해야 한다.

각 정점에서 인접한 영역 끼리는 다른 집합이라고 간주한다.

인접한 영역끼리 같은 집합에 속해있으면 이분 그래프가 아닌거다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, v, e, k;
    static String answer;
    static int[][] board;
    static int[] arr;
    static long[] dp;
    static int[] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<ArrayList<Integer>> list;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        k = kb.nextInt();
        for(int i = 0; i < k; i++) {
            int v = kb.nextInt(); // 정점의 갯수
            int e = kb.nextInt(); // 간선의 갯수

            list = new ArrayList<>();

            for(int j = 0; j <= v; j++) list.add(new ArrayList<>());

            for(int j = 0; j < e; j++) {
                int a = kb.nextInt();
                int b = kb.nextInt();
                list.get(a).add(b);
                list.get(b).add(a);
            }

            visited = new int[v+1];

            answer = "YES";
            //이분 그래프 확인을 위해 모든 정점 확인
            for(int j = 1; j <= v; j++) {
                if(visited[j] == 0) {
                    if(!T.solution(j)) break;
                }
            }
            System.out.println(answer);
        }
    }


    private boolean solution(int v) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        visited[v] = 1;

        while(!q.isEmpty()) {
            int cv = q.poll();
            for(int i = 0; i < list.get(cv).size(); i++) {
                int nv = list.get(cv).get(i);
                if(visited[cv] == visited[nv]) {
                    answer = "NO";
                    return false;
                }
                if(visited[nv] == 0) {
                    visited[nv] = visited[cv] * -1;
                    q.offer(nv);
                }
            }
        }
        return true;
    }

}