package graphs;
import java.util.*;
public class AdjacencyMatrixGraph {
	boolean [] [] g; // g[v][w]==true when there is an edge from v to w
	
	// constructor goes here

	// returns a list of nodes of the graph such that if v precedes w in the list,
	// then there is no edge from w to v
	// Such a thing is possible if and only if the graph has no cycles
	// If the graph has cycles, returns null
	
	Iterable<Integer> topologicalSort () {

		boolean [] removed = new boolean[g.length];
		Queue<Integer> output = new LinkedList<Integer>();
		
		for (int i = 0; i<g.length; i++) {
			int v = findNodeWithNoIncomingEdges(removed);
			if (v==-1)
				return null;
			output.add(v);
			removed[v]=true;
		}			
		return output;
	}
	
	private int findNodeWithNoIncomingEdges (boolean[] removed) {
		for (int v = 0; v<g.length; v++) {
			if (!removed[v] && !hasIncomingEdges(v, removed))
				return v;
		}
		return -1;
	}
	
	private boolean hasIncomingEdges(int v, boolean [] removed) {
		for (int w = 0; w<g.length; w++) {
			if (!removed[w] && g[w][v])
				return true;
		}
		return false;
	}
	
}