# Topological Sorting

## Problem

Given an directed graph, a topological order of the graph nodes is defined as follow:

• For each directed edge A -> B in graph, A must before B in the order list.
• The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Notice: You can assume that there is at least one topological order in the graph.

## Example

For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...

## Code - Java

/**
* Definition for Directed graph.
* class DirectedGraphNode {
* int label;
* ArrayList<DirectedGraphNode> neighbors;
* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*/
public class Solution {
/**
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
ArrayList<DirectedGraphNode> result = new ArrayList<>();
Map<Integer, Integer> indegree = new HashMap<>();

for (DirectedGraphNode node : graph) {
for (DirectedGraphNode neighbor : node.neighbors) {
int cnt = indegree.containsKey(neighbor.label) ? indegree.get(neighbor.label) : 0;
indegree.put(neighbor.label, cnt + 1);
}
}

for (DirectedGraphNode node : graph) {
if (!indegree.containsKey(node.label)) {
}
}

while (!queue.isEmpty()) {
DirectedGraphNode node = queue.poll();
for (DirectedGraphNode neighbor : node.neighbors) {
int cnt = indegree.get(neighbor.label);
if (cnt == 1) {
}