import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.StringTokenizer; public class Main { static boolean[] visited; static ArrayList> graph; static HashSet set1; static HashSet set2; static boolean answer = true; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int count = Integer.parseInt(br.readLine()); for (int i = 0; i < count; i++) { StringTokenizer st = new StringTokenizer(br.readLine(), " "); graph = new ArrayList<>(); set1 = new HashSet<>(); set2 = new HashSet<>(); int node = Integer.parseInt(st.nextToken()); int line = Integer.parseInt(st.nextToken()); visited = new boolean[node+1]; for (int j = 0; j <= node; j++) graph.add(new ArrayList<>()); HashSet set = new HashSet<>(); for (int j = 0; j < line; j++) { st = new StringTokenizer(br.readLine(), " "); int parent = Integer.parseInt(st.nextToken()); int child = Integer.parseInt(st.nextToken()); set.add(parent); set.add(child); graph.get(parent).add(child); graph.get(child).add(parent); } for (int j = 0; j <= node; j++) Collections.sort(graph.get(j)); for (int j = 1; j <= node; j++) { if(set.contains(j) && !visited[j]) {// 1부터 확인함. 없으면 스킵 set1.add(j); visited[j] = true; // 방문 완료 dfs(j); if (!answer) { System.out.println("NO"); break; } } } if(answer) System.out.println("YES"); } } public static void dfs(int start) { for (Integer current : graph.get(start)) { if(!visited[current]) { if(set1.contains(start)) { set2.add(current); } else set1.add(current); visited[current] = true; dfs(current); } else if(set2.contains(current) && set2.contains(start) || set1.contains(current) && set1.contains(start)) { answer = false; } } } }

제출 #105500

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: