import java.io.*;
import java.util.*;
import entsal.EntradaEstandar;
import entsal.TecladoEstandar;

public class Main {
	public static void main(String[] args)throws IOException {
		int size;
		SortedSet sol=new TreeSet();
		Grafo g;
		EntradaEstandar e = new TecladoEstandar();
		System.out.println("Introduzca el tamaño del grafo: ");
		size = (int) e.leerNumero();
		/*Pila verticescorte=new Pila(size);*/
		g = new Grafo(size);
		g.getGrafo(size);
		g.desdobla(size);
		g.muestraGrafo(size);
		sol=separacionbloques(g,size);
		sol.toString();
	}

	public static SortedSet separacionbloques (Grafo g,int size)
	{
		/*boolean[]P=new boolean[size];*/
		SortedSet solucion=new TreeSet();
		int[] dfi=new int[size];
		int[] m  =new int[size];
		int[] Padre=new int[size];
		/*Pila S=new Pila(size);*/
		boolean[][]aristas=new boolean[size][size];
		boolean encontrado;
		int i,v=-1,r=-1,u=-1;
		for(int l=0;l<size;l++)
			for(int p=0;p<size;p++)
				aristas[l][p]=false;
		for(int k=0;k<size;k++)
		{
			Padre[k]=0;
			dfi[k]=0;
		}
		i=0;
		encontrado=buscaj(v,r,dfi,size);
		i++;
		dfi[v]=i;
		m[v]=i;
		while(encontrado)
		{
			if(quedanaristas(v,g,size,aristas,u))
			{
				if(dfi[u]==0)
				{
					Padre[u]=v;
					v=u;
					i++;
					dfi[v]=i;
					m[v]=i;
				}else{
					m[v]=minimo(m[v],dfi[Padre[v]]);
				}
			}else{
				if(Padre[v]!=r)
				{
					if(m[v]<dfi[Padre[v]])
					{
						m[Padre[v]]=minimo(m[v],m[Padre[v]]);
					}else{
						solucion.add(new Integer(Padre[v]));
						v=Padre[v];
					}
				}else{
					solucion.add(new Integer(r));
					if(!quedanAristasder(r,g,aristas,size))
					{
						encontrado=buscaj(v,r,dfi,size);
						i++;
						dfi[v]=i;
						m[v]=i;
					}
				}
			}
		}
		return solucion;
	}		
			
			
			
			
			
			
			
public static boolean quedanaristas(int v,Grafo g,int size, boolean[][] aristas,int u)
{
	boolean quedan=false;
	int j=0;
	while(j<size && !quedan)
	{
		if(g.grafo[v][j]==1)
			if(aristas[v][j]==false)
			{
				quedan=true;
				aristas[v][j]=true;
				u=j;
			}
		j++;
	}
	return quedan;
}
public static int minimo(int a, int b)
{
	if(a<b)
	{
		return a;
	}else
	{
		return b;
	}
	
}
public static boolean buscaj(int v,int r, int[]dfi,int size)
{
	boolean enc=false;
	int j=0;
	while((j<size)&&(!enc))
	{
		if(dfi[j]==0)
		{
			enc=true;
			v=j;
			r=j;
		}
		j++;
	}
	return enc;
}
public static boolean quedanAristasder(int r,Grafo g,boolean[][] aristas,int size)
{
	boolean quedan=false;
	int j=0;
	while(j<size && !quedan)
	{
		if(g.grafo[r][j]==1)
			if(aristas[r][j]==false)
			{
				quedan=true;
			}
		j++;
	}
	return quedan;
}
}