kingsubin

import java.io.*;
import java.util.*;
 
public class boj_1707 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static Queue<Integer> q;
    static int[] check;
    static ArrayList<Integer>[] list;
    static int K, V, E, x, y, vertex;
    static boolean isBipartite;
 
    public static void main(String[] args) throws IOException {
        K = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < K; i++) {
            input();
            solve();
        }
 
        bw.flush();
    }
 
    static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
 
        list = new ArrayList[V+1];
        check = new int[V+1];
        isBipartite = true;
 
        for (int i = 1; i <= V; i++) {
            list[i] = new ArrayList<Integer>();
        }
 
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
 
            list[x].add(y);
            list[y].add(x);
        }
    }
 
    static void solve() throws IOException {
        for (int i = 1; i <= V; i++) {
            if (!isBipartite) { // false임이 먼저 밝혀진다면
                break;
            }
 
            if (check[i] == 0) { // 방문하지 않았다면 탐색 시작
                bfs(i, 1);
            }
        }
 
        if (isBipartite) bw.write("YES\n");
        else bw.write("NO\n");
    }
 
    static void bfs(int start, int btn) {
        q = new LinkedList<>();
 
        q.offer(start);
        check[start] = btn; // 초기값 1
 
        while (!q.isEmpty() && isBipartite) {
            vertex = q.poll();
 
            for (int next : list[vertex]) {
                if (check[next] == 0) { // 방문하지 않은 정점이라면
                    check[next] = check[vertex] * -1; // -1을 곱해 번갈아가며 체크
                    q.offer(next);
                } // 중간에 이분그래프가 아님이 밝혀진다면
                else if (check[vertex] + check[next] != 0) {
                    isBipartite = false;
                    return;
                }
            }
        }
    }
}
 

 

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

 

 

이런 느낌

 

- 어떻게 이분그래프인지 구분할까 ?

   한 정점에서 탐색을 시작하면서 스위치처럼  -1, 1 로 메모

   정점 X가 1이면 정점 X와 인접한 정점들은 -1로 체크 

   만약 두 정점의 합이 0이 아니라면 인접한 정점이 자신과 동일한 스위치로 되어있으니 이분그래프가 아님

   

 

 

---

www.acmicpc.net/problem/1707