[백준] 1707번 이분 그래프

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

1707번: 이분 그래프

이분 그래프 : 정점을 두개의 그룹으로 분할하여 다른 그룹의 정점끼리는 연결되지 않는 그래프

인접한 노드 중에 자신과 같은 번호가 있다면 이분 그래프를 만들 수 없음(다시 자신번호로 연결되는 경우)

StringBuilder 객체로 답을 제출했을 때 계속 출력초과가 나옴 

이유는 아직 모르겠음..

 

import java.util.*;
import java.io.*;

public class Main {

    // 테스트 케이스 개수
    static int K;
    // 그래프 정점의 개수
    static int V;
    // 간선의 개수
    static int E;

    static ArrayList<Integer>[] list;
    static int[] visit;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        K = Integer.parseInt(br.readLine());
        for(int j = 0; j < K; j++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());

            list = new ArrayList[V+1];
            for(int i = 0; i < list.length; i++) {
            	list[i] = new ArrayList<>();
            }
            visit = new int[V+1];
            Arrays.fill(visit, -1);

            for(int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                list[a].add(b);
                list[b].add(a);
            }
                //bfs
                boolean flag = true;
            for(int i = 1; i <= V; i++) {
                // 방문 X
                if(visit[i] == -1) {
                    if(!bfs(i)) {
                    	flag = false;
                    break;
                    }
                }
            }
            
            if(flag) {
            	bw.write("YES\n");
            } else {
            	bw.write("NO\n");
            }
        }
        bw.close();
        br.close();
    }

    public static boolean bfs(int index) {
        Queue<Integer> q = new LinkedList<>();
        visit[index] = 1;
        q.offer(index);
        while(!q.isEmpty()) {
        int node = q.poll();
            for(int next : list[node]) {

                // 방문 x 라면 q에 넣음
                if(visit[next] == -1) {
                    q.offer(next);
                    visit[next] = (visit[node] == 1) ? 2 : 1;
                } 

                if(visit[next] ==(visit[node])) {
                    return false ;
                }
            }
        }
        return true;
    } 


}