import java.util.ArrayList; import java.util.Iterator; import java.util.Scanner; public class kon { static Node[] nodes; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(); nodes = new Node[n + 1]; for (int i = 0; i < m; i++) { int a = sc.nextInt(), b = sc.nextInt(); Node nodeA = getOrCreate(a); Node nodeB = getOrCreate(b); nodeA.out.add(nodeB); nodeB.in.add(nodeA); } // Optimize graph while (true) { int counter = 0; for (int i = 1; i <= n; i++) { Node node = nodes[i]; if (node != null && (node.out.isEmpty() || node.in.isEmpty())) { counter += removeNode(node); } } if (counter == 0) { break; } } /*for (int i = 1; i <= n; i++) { Node node = nodes[i]; if (node != null && !node.dead) { System.out.println("Node: " + node + " Out: " + node.out + " In: " + node.in); } }*/ ArrayList<ArrayList<Node>> total = new ArrayList<ArrayList<Node>>(); for (int i = 1; i <= n; i++) { Node node = nodes[i]; if (node != null && !node.dead) { ArrayList<Node> initPath = new ArrayList<Node>(); initPath.add(node); dfs(node, node, initPath, total); } } if (total.size() == 0) { System.out.println("NIE"); return; } int expectedCount = total.size(); int[] nodesCount = new int[n + 1]; for (ArrayList<Node> path : total) { for (Node node : path) { nodesCount[node.n] += 1; } } StringBuilder sb = new StringBuilder(32); int idx = 0; for (int i = 1; i <= n; i++) { if (nodesCount[i] == expectedCount) { idx += 1; sb.append(nodes[i]).append(' '); } } System.out.println(idx); System.out.println(sb); } static void dfs(Node node, Node initNode, ArrayList<Node> path, ArrayList<ArrayList<Node>> total) { for (Node outNode : node.out) { if (outNode.n == initNode.n) { total.add(path); } else if (!path.contains(outNode)) { ArrayList<Node> newPath = new ArrayList<Node>(path); newPath.add(outNode); dfs(outNode, initNode, newPath, total); } } } static int removeNode(Node node) { int counter = 0; Iterator<Node> outIterator = node.out.iterator(); while (outIterator.hasNext()) { Node n = outIterator.next(); if (n.in.remove(node)) { counter += 1; } outIterator.remove(); } Iterator<Node> inIterator = node.in.iterator(); while (inIterator.hasNext()) { Node n = inIterator.next(); if (n.out.remove(node)) { counter += 1; } inIterator.remove(); } node.dead = true; return counter; } static Node getOrCreate(int n) { if (nodes[n] == null) { nodes[n] = new Node(n); } return nodes[n]; } static class Node { private int n; private boolean dead; private ArrayList<Node> out = new ArrayList<Node>(); private ArrayList<Node> in = new ArrayList<Node>(); Node(int n) { this.n = n; } @Override public boolean equals(Object obj) { return n == ((Node) obj).n; } @Override public int hashCode() { return Integer.valueOf(n).hashCode(); } @Override public String toString() { return "" + n; } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | import java.util.ArrayList; import java.util.Iterator; import java.util.Scanner; public class kon { static Node[] nodes; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(); nodes = new Node[n + 1]; for (int i = 0; i < m; i++) { int a = sc.nextInt(), b = sc.nextInt(); Node nodeA = getOrCreate(a); Node nodeB = getOrCreate(b); nodeA.out.add(nodeB); nodeB.in.add(nodeA); } // Optimize graph while (true) { int counter = 0; for (int i = 1; i <= n; i++) { Node node = nodes[i]; if (node != null && (node.out.isEmpty() || node.in.isEmpty())) { counter += removeNode(node); } } if (counter == 0) { break; } } /*for (int i = 1; i <= n; i++) { Node node = nodes[i]; if (node != null && !node.dead) { System.out.println("Node: " + node + " Out: " + node.out + " In: " + node.in); } }*/ ArrayList<ArrayList<Node>> total = new ArrayList<ArrayList<Node>>(); for (int i = 1; i <= n; i++) { Node node = nodes[i]; if (node != null && !node.dead) { ArrayList<Node> initPath = new ArrayList<Node>(); initPath.add(node); dfs(node, node, initPath, total); } } if (total.size() == 0) { System.out.println("NIE"); return; } int expectedCount = total.size(); int[] nodesCount = new int[n + 1]; for (ArrayList<Node> path : total) { for (Node node : path) { nodesCount[node.n] += 1; } } StringBuilder sb = new StringBuilder(32); int idx = 0; for (int i = 1; i <= n; i++) { if (nodesCount[i] == expectedCount) { idx += 1; sb.append(nodes[i]).append(' '); } } System.out.println(idx); System.out.println(sb); } static void dfs(Node node, Node initNode, ArrayList<Node> path, ArrayList<ArrayList<Node>> total) { for (Node outNode : node.out) { if (outNode.n == initNode.n) { total.add(path); } else if (!path.contains(outNode)) { ArrayList<Node> newPath = new ArrayList<Node>(path); newPath.add(outNode); dfs(outNode, initNode, newPath, total); } } } static int removeNode(Node node) { int counter = 0; Iterator<Node> outIterator = node.out.iterator(); while (outIterator.hasNext()) { Node n = outIterator.next(); if (n.in.remove(node)) { counter += 1; } outIterator.remove(); } Iterator<Node> inIterator = node.in.iterator(); while (inIterator.hasNext()) { Node n = inIterator.next(); if (n.out.remove(node)) { counter += 1; } inIterator.remove(); } node.dead = true; return counter; } static Node getOrCreate(int n) { if (nodes[n] == null) { nodes[n] = new Node(n); } return nodes[n]; } static class Node { private int n; private boolean dead; private ArrayList<Node> out = new ArrayList<Node>(); private ArrayList<Node> in = new ArrayList<Node>(); Node(int n) { this.n = n; } @Override public boolean equals(Object obj) { return n == ((Node) obj).n; } @Override public int hashCode() { return Integer.valueOf(n).hashCode(); } @Override public String toString() { return "" + n; } } } |