import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.StringTokenizer; public class Main { static int N, rootNode=-1; static boolean result[] = new boolean[10000]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; StringBuilder sb = new StringBuilder(); int case_num=0; List result = new ArrayList(); while (true) { List edges = new ArrayList<>(); int checked=0; while ((line = br.readLine()) != null) { StringTokenizer st = new StringTokenizer(line); boolean end = false; while (st.hasMoreTokens()) { int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); if (u == -1 && v == -1) { for (int i = 0; i < result.size(); i++) { if(result.get(i)==1) sb.append("Case "+(i+1)+" is a tree.\n"); else sb.append("Case "+(i+1)+" is not a tree.\n"); } sb.deleteCharAt(sb.length()-1); System.out.println(sb); return; } if (u == 0 && v == 0) { end = true; case_num++; break; } edges.add(new int[]{u, v}); } if (end) break; } Set set = new HashSet(); Set p_set = new HashSet(); if(checked==0) { for (int[] is : edges) { int set_size = set.size(); set.add(is[1]); p_set.add(is[0]); if(set_size==set.size()) { if(checked==0) { result.add(-1); checked=1; break; } } } } if(checked==0) { p_set.removeAll(set); if (p_set.size() > 1) { result.add(-1); checked = 1; } else if(p_set.size()==1) { rootNode = p_set.iterator().next(); } } if(checked==0) { int maxNode = 0; for (int n : set) { if (n > maxNode) maxNode = n; } boolean[] arr = new boolean[maxNode + 1]; int startNode; if(!set.isEmpty()) { if(set.size()==1) { result.add(1); checked = 1; } else if(rootNode==-1) { result.add(-1); checked = 1; } else { startNode = rootNode; arr[startNode] = true; for (int i = 0; i < set.size(); i++) { for (int[] edge : edges) { if (arr[edge[0]] || arr[edge[1]]) { arr[edge[0]] = true; arr[edge[1]] = true; } } } for (int n : set) { if (!arr[n]) { result.add(-1); checked = 1; break; } } } } else { result.add(1); checked=1; } } if(checked==0) { result.add(1); } } } }

제출 #39234

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: