UVa Online Judge Challenge "10305"
This problem presents a DAG and the solution requires implementing a topological sort. I noticed that a topological sort can be implemented using only boolean arrays so I used this as an opportunity to finally get around to using Java's BitSet class. The virtual judge run time was 0.050s.
Problem
My Solution
1/* * * * *
2Tristan Madden
32018-04-26
4https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1246
5* * * * **/
6
7import java.io.IOException;
8import java.io.InputStreamReader;
9import java.io.StreamTokenizer;
10import java.util.BitSet;
11import java.util.Stack;
12class Main {
13 static MyGraph graph;
14 static TurboReader tr = new TurboReader();
15 public static void main(String[] args) throws IOException {
16 while (true) {
17 int m = tr.nextIntUnsafe();
18 int n = tr.nextIntUnsafe();
19 if (m == 0 && n == 0) {
20 break;
21 }
22 graph = new MyGraph(m);
23 for (int i = 0; i < n; i++) {
24 int x = tr.nextIntUnsafe();
25 int y = tr.nextIntUnsafe();
26 graph.addEdge(x - 1, y - 1);
27 }
28 //System.out.println(Arrays.deepToString(graph.adjacency_matrix).replace("], ", "]\n").replace("[[", "[").replace("]]", "]"));
29 graph.topologicalSort();
30 }
31 }
32}
33class MyGraph {
34 int size;
35 BitSet adjacency_matrix;
36 BitSet visited;
37 Stack<Integer> finishing_times;
38 MyGraph(int _size) {
39 this.size = _size;
40 this.adjacency_matrix = new BitSet(size * size);
41 this.visited = new BitSet(size);
42 }
43 void addEdge(int x, int y) {
44 adjacency_matrix.set(x * size + y, true);
45 }
46 /*
47 |* I've loosely modeled Topological Sort after this YouTube video:
48 |* https://www.youtube.com/watch?v=HR_aJ1TUw4g
49 |* Step 1:
50 |* Run DFS
51 |* Step 2:
52 |* Output the reverse of finishing times of vertices
53 */
54 void topologicalSort() {
55 finishing_times = new Stack<>();
56 for (int v = 0; v < size; v++) {
57 if (visited.get(v) == false) {
58 runDFS(v);
59 }
60 }
61 while (finishing_times.isEmpty() == false) {
62 System.out.print(finishing_times.pop() + " ");
63 }
64 System.out.println("");
65 }
66 void runDFS(int v) {
67 visited.set(v, true);
68 for (int w = v; w < size; w++) {
69 if (adjacency_matrix.get(v * size + w) == true && visited.get(w) == false) {
70 runDFS(w);
71 }
72 }
73 finishing_times.push(v + 1);
74 }
75}
76class TurboReader {
77 static InputStreamReader isr;
78 static StreamTokenizer st;
79 TurboReader() {
80 isr = new InputStreamReader(System.in);
81 st = new StreamTokenizer(isr);
82 }
83 int nextIntUnsafe() throws IOException {
84 st.nextToken();
85 return (int) st.nval;
86 }
87}