-
Notifications
You must be signed in to change notification settings - Fork 0
/
RareOrder.java
123 lines (107 loc) · 2.91 KB
/
RareOrder.java
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
/**
* https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=3140
* #topological-sort
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
class RareOrder {
public static boolean topoSorting(
ArrayList<ArrayList<Integer>> graph, int[] inDegree, ArrayList<Integer> resultArr) {
Deque<Integer> zeroInDegree = new LinkedList<>();
int sz = graph.size();
boolean[] visitedArr = new boolean[sz];
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) {
zeroInDegree.add(i);
}
}
while (!zeroInDegree.isEmpty()) {
int node = zeroInDegree.poll();
resultArr.add(node);
visitedArr[node] = true;
for (int neighbour : graph.get(node)) {
if (!visitedArr[neighbour]) {
inDegree[neighbour] -= 1;
if (inDegree[neighbour] == 0) {
zeroInDegree.add(neighbour);
}
}
}
}
boolean ret = true;
for (int degree : inDegree) {
if (degree > 0) {
ret = false;
break;
}
}
return ret;
}
// return -1 if word2 is prefix of word1, 20(max size of a word) if word1 is prefix of word2, or
// index at which word1 differ word2.
static int getDiffIndex(String word1, String word2) {
int ret = -1;
int idx = 0;
if (word1.contains(word2)) {
return ret;
}
while (idx < word1.length() && idx < word2.length()) {
if (word1.charAt(idx) != word2.charAt(idx)) {
ret = idx;
break;
}
idx++;
}
if (ret == -1 && word1.length() <= word2.length()) {
ret = 20;
}
return ret;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int sz = 'Z' - 'A' + 1;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < sz; i++) {
graph.add(new ArrayList<>());
}
ArrayList<Integer> resultArr = new ArrayList<>();
int[] inDegree = new int[sz];
Arrays.fill(inDegree, -1);
int diffIdx;
int u, v;
String word1 = "", word2;
while (true) {
word2 = sc.next();
if (word2.equals("#")) {
break;
}
if (word1.isEmpty()) {
word1 = word2;
u = word1.charAt(0) - 'A';
inDegree[u] = 0;
continue;
}
diffIdx = getDiffIndex(word1, word2);
if (diffIdx != 20 && diffIdx != -1) {
u = word1.charAt(diffIdx) - 'A';
v = word2.charAt(diffIdx) - 'A';
graph.get(u).add(v);
if (inDegree[v] < 0) {
inDegree[v] = 1;
} else {
inDegree[v] += 1;
}
}
word1 = word2;
}
topoSorting(graph, inDegree, resultArr);
for (int i = 0; i < resultArr.size(); i++) {
System.out.print(String.format("%c", resultArr.get(i) + 'A'));
}
System.out.println();
return;
}
}