import java.util.*;

public class Graph{

	public static class UnionFind{

		public static class UNode{
			private Integer value;
			public UNode(int v){
				value = v;
			}
		}

		private HashMap<UNode,UNode> parents;
		private HashMap<Integer,UNode> uNodes;
		private HashMap<UNode,Integer> sizeMap;

		public UnionFind(int[] arr){
			parents = new HashMap<>();
			sizeMap = new HashMap<>();
			uNodes = new HashMap<>();

			for (int i=0; i<arr.length;i++ ) {
				UNode u=new UNode(arr[i]);
				parents.put(u,u);
				sizeMap.put(u,1);
				uNodes.put(arr[i],u);
			}
		}

		public UNode find(int a){
			Stack<UNode> stack = new Stack<>();
			UNode cur = uNodes.get(a);
			while(cur != parents.get(cur)){
				stack.push(cur);
				cur = parents.get(cur);
			}

			while(!stack.isEmpty()){
				parents.put(stack.pop(),cur);
			}
			return cur;
		}


		public boolean isSameSet(int a,int b){
			return find(a) == find(b);
		}

		public void union(int a,int b){
			UNode fa = find(a);
			UNode fb = find(b);

			if(fa!=fb){
				int sa = sizeMap.get(fa);
				int sb = sizeMap.get(fb);

				UNode big = sa>=sb ? fa : fb;
				UNode small = big==fa ? fb : fa;

				parents.put(small,big);
				sizeMap.put(big,sa+sb);
				sizeMap.remove(small);

			}
		}
	}



	public static class Node{
		public int value;
		public int in;
		public int to;
		public List<Edge> edges;
		public List<Node> nexts;

		public Node(int v,int i,int t,List<Edge> e,List<Node> n){
			value=v;
			in = i;
			to =t;
			edges=e;
			nexts=n;
		}


	}

	public static class Edge{
		private int weight;
		private Node from ;
		private Node to;

		public Edge(int w,Node f,Node t){
			weight=w;
			from=f;
			to=t;
		}
	}

	private HashMap<Integer,Node> nodes;
	private HashSet<Edge> edges;

	public Graph(){
		nodes = new HashMap<>();
		edges = new HashSet<>();
	}

	public void add(int[][] arr){
		for (int i=0; i<arr.length; i++) {
			Node f = nodes.get(arr[i][1]);
			Node t = nodes.get(arr[i][2]);

			if(f==null){

				List<Node> nList = new ArrayList<>();
				List<Edge> eList = new ArrayList<>();
				f = new Node(arr[i][1],0,1,eList,nList);
				nodes.put(arr[i][1],f);
			}else{
				f.to++;
			}

			if(t == null){
				List<Edge> eList = new ArrayList<>();
				List<Node> nList = new ArrayList<>();
				t = new Node(arr[i][2],1,0,eList,nList);
				nodes.put(arr[i][2],t);
			}else{
				t.in++;
			}

			Edge e = new Edge(arr[i][0],f,t); 
			edges.add(e);

			f.edges.add(e);
			f.nexts.add(t);
		}
		
	}


	public void BFS(){
		Queue<Node> queue = new LinkedList<>();
		HashSet<Node> exist=new HashSet<>();
		for (Node node : nodes.values() ) {
			queue.offer(node);
			while(!queue.isEmpty()){
				Node cur = queue.poll();
				if(!exist.contains(cur)){
					exist.add(cur);
					System.out.print(cur.value+",");
					for (Node n : cur.nexts) {
						queue.offer(n);
					}
				}
			}
			System.out.println();
		}
	}


	public void DFS(){
		Stack<Node> stack = new Stack<>();
		HashSet<Node> exist = new HashSet<>();

		for (Node node : nodes.values()) {
			if(!exist.contains(node)){
				stack.push(node);
				exist.add(node);
				System.out.print(node.value+",");

				while(!stack.isEmpty()){
					Node cur = stack.pop();
					for (Node next: cur.nexts) {
						if(!exist.contains(next)){
							stack.push(cur);
							stack.push(next);
							exist.add(next);
							System.out.print(next.value+",");
							break;
						}
					}
				}
			}
		}
	}

	public static class WeightCompar implements Comparator<Edge>{

		@Override
		public int compare(Edge e1,Edge e2){
			return e1.weight - e2.weight;
		}
	}

	public List<Edge> Kruskal(){
		int[] arr=new int[nodes.values().size()];
		int index=0;
		for (Node node : nodes.values()) {
			arr[index++] = node.value;
		}

		UnionFind union=new UnionFind(arr);
		PriorityQueue<Edge> queue = new PriorityQueue<>(new WeightCompar());

		for (Edge e : edges) {
			queue.add(e);
		}
		List<Edge> result = new ArrayList<>();

		while(!queue.isEmpty()){
			Edge curr = queue.poll();
			if(!union.isSameSet(curr.from.value,curr.to.value)){
				result.add(curr);
				union.union(curr.from.value,curr.to.value);
			}
		}
		return result;
	}


	public List<Node> topologicalSort(){
		List<Node> result = new ArrayList<>();


		Stack<Node> stack = new Stack<>();
		for (Node node : nodes.values() ) {
			if(node.in ==0){
				stack.push(node);
			}
		}

		while(!stack.isEmpty()){
			Node curr = stack.pop();
			result.add(curr);
			System.out.print(curr.value+",");

			for (Node next : curr.nexts) {
				--next.in;
				if(next.in ==0){
					stack.push(next);
				}
			}
		}
		return result;
	}


	public static void main(String[] args){
		Graph g = new Graph();
		int[][] arr=new int[][]{
			{4,1,4},
			{2,4,2},
			{40,3,4},
			{9,4,5},
			{2,1,3},
			{1,12,17},
			{11,12,13},
			{1,3,7},
			{7,5,9},
			{5,2,8},
			{100,8,17},
			{5,2,7},
			{1,17,13}
		};
		g.add(arr);
		g.DFS();
		System.out.println();
		List<Edge> eArray = g.Kruskal();
		for (Edge e:eArray) {
			System.out.println(e.from.value+"--->"+e.to.value);
		}

		g.topologicalSort();
	}

}