(SPOJ) Topological Sorting - Solution

I implemented this solution for the problem Topological Sorting. However, once the time limit is 0.100s, the time is very short for a Java solution using Topological Sorting. Consequently, there is not any Java solution accepted for this problem and, of course, this solution also did not pass.

Although I did not get this solution to be accepted, I decided to share how I solved it. I used the Topological Sorting algorithm and, once the problem asks: "If there are multiple solutions print the one, whose first number is smallest, if there are still multiple solutions, print the one whose second number is smallest, and so on.", I used a Priority Queue.
 

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

class Main  {
    public static HashMap<Integer, ArrayList<Integer>> adjListOut = new HashMap<Integer, ArrayList<Integer>>();
   
    public static void printAsnwer(BufferedWriter bw, int numTasks, ArrayList<Integer> seqTasks) throws NumberFormatException, IOException {
        if (seqTasks.size() < numTasks) {
            bw.write("Sandro fails.\n");
        }
        else {
            for (int i = 0; i < seqTasks.size()-1; i++) {
                bw.write(seqTasks.get(i) + " ");
            }
            bw.write(seqTasks.get(seqTasks.size()-1) + "\n");
        }
    }
   
    public static void toposort(int numTasks, int[] degrees, ArrayList<Integer> seqTasks) {
        Queue<Integer> zeroDegree = new PriorityQueue<Integer>();
        for (int i = 1; i <= numTasks; i++) {
            if (degrees[i] == 0) {
                zeroDegree.add(i);
            }
        }
       
        while (zeroDegree.size() > 0) {
            int currTask = zeroDegree.poll();
            seqTasks.add(currTask);
            ArrayList<Integer> list = adjListOut.get(currTask);
            for (int i = 0; i < list.size(); i++) {
                degrees[list.get(i)]--;
                if (degrees[list.get(i)] == 0) {
                    zeroDegree.add(list.get(i));
                }
            }
        }
    }
   
    public static void readDependencies(BufferedReader br, int numDependencies, int[] degrees) throws NumberFormatException, IOException {
        for (int i = 0; i < numDependencies; i++) {
            int task1 = reader(br);
            int task2 = reader(br);
            adjListOut.get(task1).add(task2);
            degrees[task2]++;
        }
    }
   
    public static void initAdjList(int numTasks) {
        for (int i = 1; i <= numTasks; i++) {
            adjListOut.put(i, new ArrayList<Integer>());
        }
    }
   
    static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;      
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            } 
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numTasks = reader(br);
        int numDependencies = reader(br);
       
        initAdjList(numTasks);
       
        int[] degrees = new int[numTasks+1];
        readDependencies(br, numDependencies, degrees);
       
        ArrayList<Integer> seqTasks = new ArrayList<Integer>();
        toposort(numTasks, degrees, seqTasks);
       
        printAsnwer(bw, numTasks, seqTasks);
       
        bw.flush();
        bw.close();
               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Dash Insert II - Solução

(Coderbyte) Run Length - Solução

(Coderbyte) Counting Minutes I - Solução