fork(1) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
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
copy 
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)
https://ideone.com/dO8Km9
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!