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>();
		int [] numIncomingEdges = new int [g.length];
		
		// initialize numIncomingEdges
		for (int v = 0; v<g.length; v++)
			for (int w=0; w<g[v].length; w++)
				if (g[v][w])
					numIncomingEdges[w]++;
		
		
		for (int i = 0; i<g.length; i++) {
			int v = findNodeWithNoIncomingEdges(removed, numIncomingEdges);
			if (v==-1)
				return null;
			output.add(v);
			removed[v]=true;
			for (int w = 0; w<g[v].length; w++)
				if(g[v][w]) // if there is an edge between v and w then certainly w hasn't been removed yet
					numIncomingEdges[w]--;
		}			
		return output;
	}
	
	private int findNodeWithNoIncomingEdges (boolean[] removed, int [] numIncomingEdges) {
		for (int v = 0; v<g.length; v++) {
			if (!removed[v] && numIncomingEdges[v]==0)
				return v;
		}
		return -1;
	}
	
	
}