(SPOJ) Orkut - Solution

You can check another solution for this problem here.

In the previous solution, I used an adjacency matrix. Now, I used an adjacency list. Remember that the choice between using an adjacency matrix or an adjacency list depends on the problem. If the adjacency matrix is sparse, it is usually better to use an adjacency list.

For both solutions, I used a Topological Sorting. You can find more about this topic here and here.


import java.io.*;
import java.util.*;

class Main  {
    public static HashMap<String, ArrayList<String>> adjListOut = new HashMap<String, ArrayList<String>>();
   
    public static void printAnswer(ArrayList<String> seq, int numFriends) {
        if (seq.size() == numFriends) {
            for (int i = 0; i < numFriends-1; i++) {         
                System.out.print(seq.get(i) + " ");
            }
            System.out.println(seq.get(numFriends-1));
        }
        else {
            System.out.println("impossivel");
        }
        System.out.println();
    }
   
    public static void topoSort(Queue<String> queue, ArrayList<String> seq, HashMap<String, Integer> numDependencies) {
       while (queue.size() > 0) {
            String currPerson = queue.poll();
            seq.add(currPerson);
            for (int j = 0; j < adjListOut.get(currPerson).size(); j++) {
                String name = adjListOut.get(currPerson).get(j);
                int newNumDep = numDependencies.get(adjListOut.get(currPerson).get(j))-1;
                numDependencies.put(name, newNumDep);
                if (newNumDep == 0) {
                    queue.add(name);
                }
            }
        }
    }
           
    public static void readDependencies(BufferedReader br, int numFriends, HashMap<String, Integer> numDependencies, Queue<String> queue) throws NumberFormatException, IOException {
        for (int i = 0; i < numFriends; i++) {
            String listDep = br.readLine();
            String[] listDepSplit = listDep.split(" ");
            String name = listDepSplit[0];
            int qteDependencies = Integer.parseInt(listDepSplit[1]);
            if (qteDependencies == 0) {
                queue.add(name);
            }
            numDependencies.put(name, qteDependencies);
            for (int j = 2; j < qteDependencies+2; j++) {
                String nameDep = listDepSplit[j];
                adjListOut.get(nameDep).add(name);
            }
        }
    }
   
    public static void readNames(BufferedReader br, HashMap<String, Integer> numDependencies, int numFriends) throws NumberFormatException, IOException {
        String names = br.readLine();
        String[] namesSplit = names.split(" ");
        for (int i = 0; i < numFriends; i++) {
            numDependencies.put(namesSplit[i], 0);
            adjListOut.put(namesSplit[i], new ArrayList<String>());
        }
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numCase = 0;
       
        int numFriends = Integer.parseInt(br.readLine());
        while (numFriends != 0) {
            System.out.println("Teste " + ++numCase);
           
            // read names
            HashMap<String, Integer> numDependencies = new HashMap<String, Integer>();
            readNames(br, numDependencies, numFriends);
           
            // read dependencies
            Queue<String> queue = new ArrayDeque<String>(); 
            readDependencies(br, numFriends, numDependencies, queue);
           
            ArrayList<String> seq = new ArrayList<String>();
            topoSort(queue, seq, numDependencies);
           
            printAnswer(seq, numFriends);
                       
            adjListOut.clear();
            numFriends = Integer.parseInt(br.readLine());
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}