fork download
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. public static void main (String[] args) throws java.lang.Exception
  11. {
  12. int testCase = 1;
  13.  
  14. Scanner sc = new Scanner(System.in);
  15.  
  16. boolean first = true;
  17. while (sc.hasNextLine()) {
  18.  
  19. if (!first)
  20. System.out.println();
  21.  
  22. first = false;
  23.  
  24. int n = sc.nextInt();
  25.  
  26. Map<String, Integer> wordToNum = new HashMap<>();
  27. Map<Integer, String> numToWord = new HashMap<>();
  28.  
  29. for (int i = 0; i < n; ++i) {
  30. String word = sc.next();
  31. wordToNum.put(word, i);
  32. numToWord.put(i, word);
  33. }
  34.  
  35. int m = sc.nextInt();
  36.  
  37. List<ArrayList<Integer>> adj = new ArrayList<>();
  38.  
  39. for (int i = 0; i < n; ++i) adj.add(new ArrayList<>());
  40.  
  41. int[] indegree = new int[101];
  42.  
  43. StringTokenizer stringTokenizer;
  44.  
  45. for (int i = 0; i < m; ++i) {
  46. String u = sc.next(), v = sc.next();
  47. adj.get(wordToNum.get(u)).add(wordToNum.get(v));
  48. indegree[wordToNum.get(v)]++;
  49. }
  50.  
  51. boolean[] vis = new boolean[101];
  52. Arrays.fill(vis, false);
  53.  
  54. PriorityQueue<Integer> queue = new PriorityQueue();
  55.  
  56. for (int i = 0; i < n; ++i) {
  57. if (indegree[i] == 0) {
  58. queue.add(i);
  59. vis[i] = true;
  60. }
  61.  
  62. }
  63.  
  64. List<Integer> topoSort = new ArrayList<>();
  65.  
  66. while (!queue.isEmpty()) {
  67. int u = queue.poll();
  68. topoSort.add(u);
  69. for (int j = 0; j < adj.get(u).size(); ++j) {
  70. if (!vis[adj.get(u).get(j)]) {
  71.  
  72. if (--indegree[adj.get(u).get(j)] == 0) {
  73. queue.add(adj.get(u).get(j));
  74. vis[adj.get(u).get(j)] = true;
  75. }
  76.  
  77. }
  78. }
  79.  
  80. }
  81.  
  82. StringBuilder sb = new StringBuilder("");
  83.  
  84. for (int i = 0; i < topoSort.size(); ++i) {
  85. if (i == 0)
  86. sb.append(numToWord.get(topoSort.get(i)));
  87. else
  88. sb.append(" " + numToWord.get(topoSort.get(i)));
  89. }
  90. System.out.println("Case #" + (testCase++) + ": Dilbert should drink beverages in this order: " + sb.toString() + ".");
  91. System.out.println();
  92.  
  93. }
  94. }
  95. }
Runtime error #stdin #stdout #stderr 0.06s 2184192KB
stdin
8
a
b
c
d
e
f
s
t
6
a e
a b
c d
e f
s t
a t

8
s
a
b
e
f
c
d
t
6
a e
a b
c d
e f
s t
a t

8
a
b
c
s
t
e
f
d
6
a b
a e
c d
e f
s t
a t
stdout
Case #1: Dilbert should drink beverages in this order: a b c d e f s t.


Case #2: Dilbert should drink beverages in this order: s a b e f c d t.


Case #3: Dilbert should drink beverages in this order: a b c s t e f d.


stderr
Exception in thread "main" java.util.NoSuchElementException
	at java.util.Scanner.throwFor(Scanner.java:862)
	at java.util.Scanner.next(Scanner.java:1485)
	at java.util.Scanner.nextInt(Scanner.java:2117)
	at java.util.Scanner.nextInt(Scanner.java:2076)
	at Ideone.main(Main.java:24)