(SPOJ) 1368 - Orkut - Solução

Para esta solução, foi utilizado o algoritmo de "Ordenação Topológica" obtido neste site.

Utilizado o TreeMap para poder associar um nome a um índice na matriz.
 
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);
    }
   
    ArrayList<Integer> ordenacaoTopologica(ArrayList<Integer> nosSemArestasEntrada, int[][] matriz, int qteAmigos, int[] vetorEntradas) {
        // Lista vazia que irá conter os elementos ordenados
        ArrayList<Integer> ordenados = new ArrayList<Integer>();
       
        // enquanto S é não-vazio faça, e
        // 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 < qteAmigos; j++) {
                if (matriz[nosSemArestasEntrada.get(i)][j] == 1) {
                    // remova a aresta 'e' do grafo
                    matriz[nosSemArestasEntrada.get(i)][j] = 0;
                    // se 'm' não tem mais arestas de entrada então
                    vetorEntradas[j]--;
                    if (vetorEntradas[j] == 0) {
                        nosSemArestasEntrada.add(j); // insira  m em S
                    }
                }
            }
        }
       
        // se o grafo tem arestas então o grafo tem pelo menos um ciclo, impossível
        if (ordenados.size() != qteAmigos) {
            ArrayList<Integer> vazio = new ArrayList<Integer>();
            return vazio;
        }
   
        return ordenados;
    }
   
    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 qteAmigos = Integer.valueOf(tokenizer.nextToken());

            if (qteAmigos == 0) {
                return;
            }
           
            // obtém nomes dos amigos
            Map<String, Integer> amigos = new TreeMap<String, Integer>();
            String[] vetAmigos = new String[qteAmigos];
            line = br.readLine();
            tokenizer = new StringTokenizer(line);
            for (Integer i = 0; i < qteAmigos; i++) {
                String nome = String.valueOf(tokenizer.nextToken());
                vetAmigos[i] = nome; // vetor usado só no final, para recuperar os nomes
                amigos.put(nome, i);
            }
           
            int[][] matrizAdj = new int[qteAmigos][qteAmigos];
            for (int i = 0; i < qteAmigos; i++) {
                for (int j = 0; j < qteAmigos; j++) {
                    matrizAdj[i][j] = 0;
                }
            }
           
             int[] vetorEntradas = new int[qteAmigos];
            for (int i = 0; i < qteAmigos; i++) {
                line = br.readLine();
                tokenizer = new StringTokenizer(line);
               
                // verifico a qual índice o nome está associado para usar na matriz
                Integer x = amigos.get(String.valueOf(tokenizer.nextToken()));
               
                int exigencia = Integer.parseInt(tokenizer.nextToken());
               
                for (int j = 0; j < exigencia; j++) {
                    // verifico a qual índice o nome está associado para usar na matriz
                    Integer y = amigos.get(String.valueOf(tokenizer.nextToken()));
                    matrizAdj[x][y] = 1;
                    vetorEntradas[y] += 1; // verifica arestas de entrada
                }
            }
           
            // 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 < qteAmigos; i++) {
                if (vetorEntradas[i] == 0) {
                    nosSemArestasEntrada.add(i);
                }
            }

            ArrayList<Integer> resultado = new ArrayList<Integer>();
           
            resultado = ordenacaoTopologica(nosSemArestasEntrada, matrizAdj, qteAmigos, vetorEntradas);
           
            contador++;
            System.out.println("Teste " + contador);
           
            if (resultado.size() == 0) {
                System.out.println("impossivel\n");
            }
            else {
                for (int i = qteAmigos-1; i > 0; i--) {
                    System.out.print(vetAmigos[resultado.get(i)] + " ");
                }
                System.out.println(vetAmigos[resultado.get(0)] + "\n");
            }
        }
                   
        return;
    }
}