(UVA) The Forrest for the Trees - Solution

I used the Union-Find approach to solve this problem.

First, I keep every edge in an ArrayList because I cannot call the union method while the letters are not related to a number. Then, when we read the list of letters (points) of the tree, we associate each letter to a number in order to use it in the union method.

In the end, I return one array with two elements in the count method. The first position of my array corresponds to the number of trees in the case, and the second position corresponds to the number of "acorns" (nodes without any edge).


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

class Main  {
    public static HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int[] count() {
        int[] v = new int[nodeParent.length+1];
       
        for (int i = 1; i < nodeParent.length; i++) {
            v[root(nodeParent[i])] += 1;   
        }
       
        int[] answers = new int[2];
        for (int i = 1; i < v.length; i++) {
            if (v[i] > 1) {
                answers[0]++;
            }   
            else if (v[i] == 1) { // if it is a node without any edge (an isolated dot)
                answers[1]++;
            }
        }
       
        return answers;
    }
   
    public static int root(int node) {
        int currNode = node;
        while (nodeParent[currNode] != currNode) {
            currNode = nodeParent[currNode];
        }
       
        return currNode;
    }
   
    public static void union(int node1, int node2) {
        int rootN1 = root(node1);
        int rootN2 = root(node2);
       
        if (rootN1 != rootN2) { // they are not connected
            if (depth[rootN1] >= depth[rootN2]) {
                nodeParent[rootN2] = nodeParent[rootN1];
                if (depth[rootN1] == depth[rootN2]) {
                    depth[rootN1] += 1; // the link between rootN1 and rootN2
                }
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
        }
    }
   
    public static void mapLettersToNumbers(int[] nodeParent, int[] depth, String nodes) {
         for (int j = 1; j <= nodes.length(); j++) {
            map.put(nodes.charAt(j-1), j);
            nodeParent[j] = j;
            depth[j] = 0;
        }
    }
   
    public static String discoverAllLetters(String line) {
        String[] letters = line.split(",");
        String nodes = "";
        for (int j = 0; j < letters.length; j++) {
            nodes += letters[j];
        }
       
        return nodes;
    }
   
    public static void readEdges(Scanner sc, ArrayList<Link> links) {
        String line = sc.next();
        while (line.charAt(0) != '*') {
            char c1 = line.charAt(1);
            char c2 = line.charAt(3);
           
            links.add(new Link(c1, c2));

            line = sc.next();
        }
    }
   
    public static void process() throws NumberFormatException, IOException {   
        Scanner sc = new Scanner(System.in);
       
        int numCases = sc.nextInt();
        for (int i = 0; i < numCases; i++) {       
            ArrayList<Link> links = new ArrayList<Link>();
            readEdges(sc, links);
           
            String line = sc.next(); // read all the letters (points)
            String nodes = discoverAllLetters(line);
           
            nodeParent = new int[nodes.length()+1];
            depth = new int[nodes.length()+1];
            mapLettersToNumbers(nodeParent, depth, nodes);
          
            for (int j = 1; j <= links.size(); j++) {
                union(map.get(links.get(j-1).source), map.get(links.get(j-1).dest));
            }
           
            int[] answer = count();
            System.out.println("There are " + answer[0] + " tree(s) and " + answer[1] + " acorn(s).");
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Link {
    char source;
    char dest;
   
    public Link(char source, char dest) {
        this.source = source;
        this.dest = dest;
    }
}