(SPOJ) 1332 - Dengue - Solução

Para esta solução, foi utilizado (com alguma alterações necessárias) o algoritmo de "Ordenação Topológica" obtido neste site.
 
import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main processando = new Main();
        processando.processa();
       
        System.exit(0);
    }
   
    int ordenacaoTopologica(ArrayList<Integer> nosSemArestasEntrada, int[][] matriz, int qtePontos, int[] vetorGrau) {
        // Lista vazia que irá conter os elementos ordenados
        ArrayList<Integer> ordenados = new ArrayList<Integer>();
       
        // enquanto S é não-vazio faça
        // remova um nodo n de S
        for (int i = 0; i < nosSemArestasEntrada.size(); i++) {
            // insira o nodo 'n' em L
            ordenados.add(nosSemArestasEntrada.get(i));
            // para cada nodo 'm' com uma aresta 'e' de 'n' até 'm' faça
            for (int j = 0; j < qtePontos; j++) {
                if (matriz[nosSemArestasEntrada.get(i)][j] == 1) {
                    // remova a aresta 'e' do grafo
                    matriz[nosSemArestasEntrada.get(i)][j] = 0;
                    matriz[j][nosSemArestasEntrada.get(i)] = 0;
                    // se 'm' não tem mais arestas de entrada então
                    vetorGrau[j]--;
                    vetorGrau[nosSemArestasEntrada.get(i)]--;
                    if (vetorGrau[j] == 1) {
                        nosSemArestasEntrada.add(j);
                    }
                }
            }
        }
    
        // soma +1 ao resultado, pois estava manipulando a partir de 0
        return ordenados.get(ordenados.size()-1)+1;
    }
   
    void processa() throws NumberFormatException, IOException {
        String line = "";
       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int contador = 0;       
        while((line = br.readLine()) != null) {
            StringTokenizer tokenizer = new StringTokenizer(line);
            int qtePontos = Integer.valueOf(tokenizer.nextToken());

            if (qtePontos == 0) {
                return;
            }
           
            contador++;
            System.out.println("Teste " + contador);
           
            // vetor para dizer o grau dos nós
            int[] vetorGrau = new int[qtePontos];
            for (int i = 0; i < qtePontos-1; i++) {
                vetorGrau[i] = 0;
            }
           
            // matriz de adjacência
            int[][] matrizAdj = new int[qtePontos][qtePontos];
            for (int i = 0; i < qtePontos; i++) {
                for (int j = 0; j < qtePontos; j++) {
                    matrizAdj[i][j] = 0;
                }
            }
           
            // preenche matriz de adjacência
            // preenche grau dos nós
            for (int i = 0; i < qtePontos-1; i++) {
                line = br.readLine();
                tokenizer = new StringTokenizer(line);
               
                int p1 = Integer.valueOf(tokenizer.nextToken());
                int p2 = Integer.valueOf(tokenizer.nextToken());
                matrizAdj[p1-1][p2-1] = 1;
                matrizAdj[p2-1][p1-1] = 1;
                vetorGrau[p1-1] += 1;
                vetorGrau[p2-1] += 1;
            }
           
            // de acordo com o grau dos nós, vê quem tem uma aresta só (é folha) ou nenhuma (no caso, se é folha, não teria aresta de entrada)
            ArrayList<Integer> nosSemArestasEntrada = new ArrayList<Integer>();
            for (int i = 0; i < qtePontos; i++) {
                if (vetorGrau[i] == 1 || vetorGrau[i] == 0) {
                    nosSemArestasEntrada.add(i);
                }
            }

            System.out.println(ordenacaoTopologica(nosSemArestasEntrada, matrizAdj, qtePontos, vetorGrau));
                                             
            System.out.println();
        }
                   
        return;
    }
}