# Java solution using DFS, very clean and easy to understand

• Step 1: Construct the graph;
Step 2: Apply DFS to each node. When we visit a node for the first time, node.start = ++timestamp; when we finished the DFS on current node, node.finish = ++timestamp;
Step 3: Sort the nodes by node.finish in descending order. This is a typical way to implement topological sort.

Note: If the order is invalid, then there must be at least one cycle in the graph. We can use DFS to detect cycles. When we visit a node during DFS, if its start time is not zero but its finish time is zero, then there must be a cycle here.

``````public class Solution {
private int timestamp;

public String alienOrder(String[] words) {
Node[] nodes = new Node[26];

for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words[i].length(); j++) {
char ch = words[i].charAt(j);
if (nodes[ch - 'a'] == null) nodes[ch - 'a'] = new Node(ch);
}
if (i == 0) continue;
for (int j = 0; j < words[i - 1].length() && j < words[i].length(); j++) {
char ch1 = words[i - 1].charAt(j);
char ch2 = words[i].charAt(j);
if (ch1 != ch2) {
break;
}
}
}

for (Node node: nodes) {
if (node != null && !DFS(node)) return "";
}

PriorityQueue<Node> queue = new PriorityQueue<Node>();
for (Node node: nodes) {
if (node != null) queue.offer(node);
}

String result = "";
while (!queue.isEmpty()) {
result += queue.poll().ch;
}

return result;
}

private boolean DFS(Node node) {
if (node.start > 0) return node.finish > 0;

node.start = ++timestamp;
for (Node n: node.set) {
if (!DFS(n)) return false;
}
node.finish = ++timestamp;

return true;
}

class Node implements Comparable<Node> {
Set<Node> set = new HashSet<Node>();
int start;
int finish;
char ch;

public Node(char ch) {
this.ch = ch;
}

@Override
public int compareTo(Node that) {
return that.finish - this.finish;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.