(URI) Rede de Fibra - Solução

For this solution, I used the Breadth-First Search instead of the Floyd-Warshall.

I do the BFS for every node in the network in order to know all the companies that arrive in any node from a specific node n. Moreover, the answer is stored in a matrix. Then, in the end, I only need to check the content for matrix[reqRow][reqCol].


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

class Main  {
    public static HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<Integer, ArrayList<Integer>>();
   
    public static String checkRepeatedLetter(String ans) {
        String newAns = "";
        for (int i = 0; i < ans.length(); i++) {
            if (newAns.indexOf(ans.charAt(i)) == -1) {
                newAns += ans.charAt(i);
            }
        }
       
        return newAns;
    }
   
    public static void giveAnswer(Scanner sc, String[][] companiesThatArriveAnswer) {
        int reqStart = sc.nextInt();
        int reqEnd = sc.nextInt();
        while (reqStart != 0 || reqEnd != 0) {
            String ans = companiesThatArriveAnswer[reqStart][reqEnd];
           
            if (ans.length() > 0) {
                // if I have a repeated letter in the answer, I only need one occurrence
                String newAns = checkRepeatedLetter(ans);
               
                // sort the answer (lexicographic order)
                // in order to sort the answer, I need to transform my string in an array
                char[] sorted = new char[newAns.length()];
                for (int i = 0; i < newAns.length(); i++) {
                    sorted[i] = newAns.charAt(i);
                }
                Arrays.sort(sorted);
                   
                for (int i = 0; i < sorted.length; i++) {
                    System.out.print(sorted[i]);
                }
                System.out.println();
            }
            else {
                System.out.println("-");
            }
                          
            reqStart = sc.nextInt();
            reqEnd = sc.nextInt();           
        }
    }
   
    public static String intersecCompanies(String currCies, String nextCies) {
        String result = "";
       
        for (int i = 0; i < nextCies.length(); i++) {
            if (currCies.indexOf(nextCies.charAt(i)) != -1) { // if currCies contains nextCies.charAt(i), there is an intersection
                result += nextCies.charAt(i);
            }   
        }
       
        return result;
    }
   
    public static boolean verify(String alreadyInNode, String probablyNewCie) {
        // if I do not have anything in my matrix of answer and there is at least one companie in the next node, I need to add the companie to the answer
        if (alreadyInNode.length() == 0 && probablyNewCie.length() > 0) {
            return true;
        }
        else {
            for (int i = 0; i < probablyNewCie.length(); i++) { // ex.: ad
                for (int j = 0; j < alreadyInNode.length(); j++) { // ex.: abc
                    if (probablyNewCie.charAt(i) == alreadyInNode.charAt(j)) {
                        break;
                    }
                    if (j == alreadyInNode.length()-1) { // if I am in the end of the second for, and it did not call 'break', then the i companie is new
                        return true;
                    }
                }
            }
        }
        return false;
    }
   
    public static void bfs(int start, String[][] companiesThatArrive, String[][] companiesThatArriveAnswer,  String allCompanies) {
        Queue<Element> queue = new ArrayDeque<Element>();
        Element e = new Element(start, allCompanies); // consider that all the companies arrive in the start node in order to do the intersection
        queue.add(e);

        while (queue.size() > 0) {
            Element currElement = queue.poll();
           
            int currNode = currElement.node;
            String currCies = currElement.cies;
           
            ArrayList<Integer> reachables = adjList.get(currNode);
            for (int i = 0; i < reachables.size(); i++) {
                // check the companies that the current node and the reachable node have in common
                String intersection = intersecCompanies(currCies, companiesThatArrive[currNode][reachables.get(i)]);
                // verify if there is at least one new companie that arrive in the reachable node in the matrix of answer
                // if the answer is positive, I need to include the new companie in my answer, and I need to add the node to my queue
                if (verify(companiesThatArriveAnswer[start][reachables.get(i)], intersection)) {
                    e = new Element(reachables.get(i), intersection);
                    companiesThatArriveAnswer[start][reachables.get(i)] += intersection;
                    queue.add(e);
                }
            }
        }
    }
   
    public static String filterCompanies(int numNodes, String companies) {
        String allCompanies = "";
        for (int i = 1; i <= numNodes; i++) {
            for (int j = 0; j < companies.length(); j++) {
                if (allCompanies.indexOf(companies.charAt(j)) == -1) {
                    allCompanies += companies.charAt(j);
                }
            }
        }
       
        return allCompanies;
    }
   
    public static String readEntries(Scanner sc, String[][] companiesThatArrive) {
        int start = sc.nextInt();
        int end = sc.nextInt();
        String allTmp = ""; // only to get all the possible companies
        while (start != 0 || end != 0) {
            String companies = sc.next();
       
            allTmp += companies; // only to get all the possible companies
            companiesThatArrive[start][end] = companies;
           
            adjList.get(start).add(end);
           
            start = sc.nextInt();
            end = sc.nextInt();
        }
       
        return allTmp;
    }
   
    public static void startAdjList(int numNodes) {
        for (int i = 1; i <= numNodes; i++) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            adjList.put(i, list);      
        }
    }
   
    public static void startMatrix(String[][] matrix, int numNodes) {
        for (int i = 1; i <= numNodes; i++) {
            for (int j = 1; j <= numNodes; j++) {
                matrix[i][j] = "";
            }
        }
    }
   
    public static void process() throws NumberFormatException, IOException {   
        Scanner sc = new Scanner(System.in);
       
        int numNodes = sc.nextInt();
       
        while (numNodes != 0) {
            String[][] companiesThatArrive = new String[numNodes+1][numNodes+1];
            String[][] companiesThatArriveAnswer = new String[numNodes+1][numNodes+1];
                       
            startMatrix(companiesThatArrive, numNodes);
            startMatrix(companiesThatArriveAnswer, numNodes);
           
            startAdjList(numNodes);
           
            // read entries and the companies
            String companies = readEntries(sc, companiesThatArrive);
                       
            // filter the possible companies - I only need one occurrence for each companie
            String allCompanies = filterCompanies(numNodes, companies);
           
            // do BFS for every node
            // I know all the companies that arrive in any node from node i
            for (int i = 1; i <= numNodes; i++) {
                bfs(i, companiesThatArrive, companiesThatArriveAnswer, allCompanies);
            }
           
            giveAnswer(sc, companiesThatArriveAnswer);
           
            System.out.println(); // blank line after each case
           
            adjList.clear();
            numNodes = sc.nextInt();
        }
                  
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Element {
    int node;
    String cies;
   
    public Element(int node, String cies) {
        this.node = node;
        this.cies = cies;
    }
}