class Main5 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); List<String> list = new ArrayList<>(); while (scanner.hasNext()) { String line = scanner.nextLine(); list.add(line); if (!line.endsWith(",")) { break; } } TreeSet<String> set = new TreeSet<>(); for (String pair : list) { String[] tmp = pair.split(",|\\{|\\}"); AddDependency(tmp[1].trim(), tmp[2].trim()); set.add(tmp[1].trim()); set.add(tmp[2].trim()); } int i = 0; for (String str : set) { if (i == set.size() - 1) { System.out.println("{" + str + ", " + MouldIsCircularDependency(str) + "}"); } else { i++; System.out.println("{" + str + ", " + MouldIsCircularDependency(str) + "},"); } } } static Map<String, ListNode> map1 = new HashMap<>(); static Map<String, ListNode> map2 = new HashMap<>(); public static void AddDependency(String moduleId, String dependModuleId) { if (map1.containsKey(moduleId)) { if (map2.containsKey(dependModuleId)) { ListNode l1 = map1.get(moduleId); ListNode l2 = map2.get(dependModuleId); l1.next = l2; } else { ListNode l1 = map1.get(moduleId); ListNode l2 = new ListNode(dependModuleId); l1.next = l2; map1.put(dependModuleId, l2); } } else { if (map2.containsKey(dependModuleId)) { ListNode l1 = new ListNode(moduleId); ListNode l2 = map2.get(dependModuleId); l1.next = l2; map1.put(moduleId, l1); } else { ListNode l1 = new ListNode(moduleId); ListNode l2 = new ListNode(dependModuleId); l1.next = l2; map1.put(moduleId, l1); map1.put(dependModuleId, l2); map2.put(dependModuleId, l2); map2.put(moduleId, l1); } } } private static boolean MouldIsCircularDependency(String moduleId) { for (Map.Entry<String, ListNode> entry : map1.entrySet()) { ListNode ring = detectCycle(entry.getValue()); ListNode curr = ring; boolean isFirst = true; while (curr != null && (curr != ring || isFirst)) { isFirst = false; if (curr.val.equals(moduleId)) { return true; } curr = curr.next; } } return false; } static void clear() { map1.clear(); map2.clear(); } public static ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode fast = head, slow = head; while (true) { if (fast == null || fast.next == null) { return null; } slow = slow.next; fast = fast.next.next; if (fast == slow) { break; } } slow = head;//slow back to start point while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; //when slow == fast, it is where cycle begins } } class ListNode { String val; ListNode next; ListNode(String val) { this.val = val; this.next = null; } }