package ejercicio1;

import java.util.List;
import java.util.Stack;
import java.util.ArrayList;
import java.util.Collections;
import utils.Grafo;
import utils.Materia;

public class Ejercicio1 {
	private Grafo grafo;
	
	public Ejercicio1() {
		grafo  = new Grafo();
	}
	
	private ArrayList< ArrayList<Materia> > kosaraju(Grafo grafo){
		ArrayList<Materia> orden = new ArrayList<Materia>();
		ArrayList<Materia> componente = new ArrayList<Materia>();
		ArrayList< ArrayList<Materia> > componentes = new ArrayList< ArrayList<Materia> >();
		boolean []usado = new boolean[grafo.size()];
		
		//recorre grafo por dfs, obtiene el numero de cada nodo
		for (int i = 0; i < usado.length; i++) {
			if (!usado[i]){
				dfs(grafo, usado, orden, i);
			}
		}
		
		//El grafo que usamos da igual invertido
		//revertir el grafo
		//Grafo grafoRevertido = reverseGraf(grafo);
		
		//recorrer grafo invertido por dfs, ordenado por nodos recorridos y no usado y devolver css's
		Collections.reverse(orden);
		
		for (Materia m : orden) {
			if (!usado[ m.getId() ]){
				dfs(grafo, usado, componente, m.getId());
				componentes.add(componente);
			}
		}
		
		return componentes;

	}
	
	private void dfs(Grafo g, boolean[] usado, List<Materia> m, int i) {
		Stack<Materia> materias = new Stack<Materia>();
		materias.push( g.getMateria(i) );
		
		while(materias.size() != 0) {
			Materia actual = materias.pop();
			List<Materia> adyacentes = actual.getAdyacentes();

			//recorre todos los vecinos no recorridos
			for (Materia vecino : adyacentes) {
				if (!usado[ vecino.getId() ]) {
					materias.push(vecino);
				}
			}

			//si no puede avanzar mas, se encola
			m.add(actual);
		}
	}
}

@@ -1170,199 +1170,268 @@
 %0A%09%0A%09
-private void dfs(Grafo g, boolean%5B%5D usado, List%3CMateria%3E m, int i) %7B%0A%09%09Stack%3CMateria%3E materias = new Stack%3CMateria%3E();%0A%09%09materias.push( g.getMateria(i) );%0A%09%09%0A%09%09while(materias.size() != 0
+/*%0A%09 * esta implementacion de dfs es recursiva!!! %0A%09 * TODO: ver si se puede implementar iterativamente, puede quedar como experimentacion ver tiempos de corrida iterativo vs recursivo%0A%09 */%0A%09private void dfs(Grafo g, boolean%5B%5D usado, List%3CMateria%3E m, int i
 ) %7B%0A
-%09
 %09%09Ma
@@ -1449,125 +1449,63 @@
 l = 
-materias.pop(
+g.getMateria(i
 );
+ 
 %0A%09%09
-%09List%3CMateria%3E adyacentes = actual.getAdyacentes();%0A%0A%09%09%09//recorre todos los vecinos no recorridos%0A%09
+usado%5B actual.getId() %5D = true;%0A%09%09%0A
 %09%09fo
@@ -1525,16 +1525,26 @@
 cino : a
+ctual.getA
 dyacente
@@ -1544,21 +1544,22 @@
 yacentes
+()
 ) %7B%0A
-%09
 %09%09%09if (!
@@ -1593,85 +1593,54 @@
 %09%09%09%09
-%09materias.push(vecino
+dfs(g, usado, m, vecino.getId()
 );%0A%09%09%09
-%09
 %7D%0A
-%09
 %09%09%7D%0A
-%0A%09%09%09//si no puede avanzar mas, se encola%0A%09
+%09%09%0A
 %09%09m.
@@ -1652,17 +1652,13 @@
 ctual);%0A
-%09%09%7D%0A
 %09%7D%0A%7D%0A

fix dfs