(URI) Dudu Faz Serviço - Solution 2

Solution using Topological Sorting to check for cycles in a graph.
 

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

class Main  {
    public static HashMap<Integer, ArrayList<Integer>> adjListOut = new HashMap<Integer, ArrayList<Integer>>(); 
   
    public static void printAnswer(BufferedWriter bw, int documentsVisited, int numDocuments) throws NumberFormatException, IOException {
        if (documentsVisited != numDocuments) {
            bw.write("SIM\n");
        }
        else {
            bw.write("NAO\n");
        }
    }
   
    public static int topoSort(Queue<Integer> zeroDegree, int[] dependencies) {
        int documentsVisited = 0;
        while (zeroDegree.size() > 0) {
            int currDocument = zeroDegree.poll();
            documentsVisited++;
            for (int j = 0; j < adjListOut.get(currDocument).size(); j++) {
                int reachDocument = adjListOut.get(currDocument).get(j);
                dependencies[reachDocument]--;
                if (dependencies[reachDocument] == 0) {
                    zeroDegree.add(reachDocument);
                }
            }
        }
       
        return documentsVisited;
    }
   
    public static void checkZeroDependencies(int numDocuments, int[] dependencies, Queue<Integer> zeroDegree) {
        for (int j = 0; j < numDocuments; j++) {
            if (dependencies[j+1] == 0) {
                zeroDegree.add(j+1);
            }
        }
    }
   
    public static void readDependencies(BufferedReader br, int numDependencies, int[] dependencies) throws NumberFormatException, IOException {
        for (int j = 0; j < numDependencies; j++) {
            int doc = reader(br);
            int dep = reader(br);
            adjListOut.get(dep).add(doc);
            dependencies[doc]++;
        }
    }
   
    public static void initAdjList(int numDocuments) {
        for (int j = 0; j < numDocuments; j++) {
            adjListOut.put((j+1), 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 numCases = reader(br);
        for (int i = 0; i < numCases; i++) {
            int numDocuments = reader(br);
            int numDependencies = reader(br);
           
            initAdjList(numDocuments);
           
            int[] dependencies = new int[numDocuments+1];
            readDependencies(br, numDependencies, dependencies);
           
            // check the documents with zero dependencies
            Queue<Integer> zeroDegree = new ArrayDeque<Integer>();
            checkZeroDependencies(numDocuments, dependencies, zeroDegree);
           
            // topological sorting
            int documentsVisited = topoSort(zeroDegree, dependencies);
           
            printAnswer(bw, documentsVisited, numDocuments);
           
            adjListOut.clear();
        }
       
        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) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução