고려사항

1. 양방향으로 접근해야한다
   (모든 간선을 정확히 검사하고, 연결된 모든 정점을 탐색하기 위해서)
2. 색깔로 구별해주자

첫번째 예시를 보면 양방향으로 리스트에 저장해주고, 처음 색깔은 RED(1)로 잡는다. 그리고 자식들을 모두 BLUE(-1)로 지정해주고 그때그때 갱신해준다. 만약 이 예시와 같이 부모와 자식의 색이 다르다면 "YES"출력!

두번째 예시를 보면 차례대로 색깔을 탐색하고 정해주다가 3에서 RED(1)가 나왔는데 4에서도 RED(1)가 나왔으므로 자식과 부모의 색이 같아진다. 이럴때 "NO"출력!

코드

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

public class g4_1707 {
    static ArrayList<Integer>[] list;
    static int v,e;
    static boolean colorcheck;//자식과 부모의 색이 같은지 다른지 체크
    static int[] colors;//노드들의 색 저장

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc=Integer.parseInt(br.readLine());
        for(int t=1;t<=tc;t++){
            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<v+1;i++){
                list[i]=new ArrayList<>();
            }

            for(int i=0;i<e;i++){
                st=new StringTokenizer(br.readLine());
                int p=Integer.parseInt(st.nextToken());
                int c=Integer.parseInt(st.nextToken());
                list[p].add(c);
                list[c].add(p);//양방향으로 검사해야 빠짐없이 검사가능
            }
            colors=new int[v+1];
            colorcheck=true;

            for(int i=1;i<v+1;i++){
                if(!colorcheck){
                    break;
                }
                if(colors[i]==0){
                    dfs(i,1);
                }
            }
            System.out.println(colorcheck ? "YES":"NO");
        }
    }

    static void dfs(int v, int color){
        colors[v]=color;
        //색이 정해지지 않은 부모의 색은 무조건 빨강

        for(int i:list[v]){
            if(colors[i]==color){
            //부모자식 색깔이 같으면 안된다!
                colorcheck=false;
                return;
            }
            if(colors[i]==0){
            //아직 색이 정해지지 않았으면 부모와 다른색을 지정해준다
                dfs(i,-color);
            }
        }
    }
}