(UVA) Virtual Friends - Solution

For this problem, I assumed that for every X relationships, I would have at most X*2 friends involved. Thus, I could have the maximum length for the arrays I would use in the Union-Find.

First, I tried to count how many nodes I had in a specific tree of friends every time I had a new relationship. This operation was very inefficient because it is possible to have until 100,000 relationships. Then, for this case (worst case), the count method would be called 100,000 times and, for every call, it would have to iterate over the 200,000 positions in my nodeParent array.

Once the solution previously described got Time Limit Exceeded, I had to think about a solution where the old count method could be done in constant time O(1). Now, I have another array which keeps the number of nodes that every root has in its tree.


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

class Main  {
    public static HashMap<String, Integer> map = new HashMap<String, Integer>();
    public static int[] nodeParent;
    public static int[] depth;
    public static int[] numNodes;
   
    public static int root(int n) {
        int currNode = n;
        while (nodeParent[currNode] != currNode) {
            currNode = nodeParent[currNode];
        }
       
        return currNode;
    }
   
    public static int union(int n1, int n2) {
        int rootN1 = root(n1);
        int rootN2 = root(n2);

        int superRoot = rootN1;
        if (rootN1 != rootN2) { // they are not connected
            if (depth[rootN1] >= depth[rootN2]) {
                int numNodesN2 = numNodes[rootN2];
                nodeParent[rootN2] = nodeParent[rootN1];
                if (depth[rootN1] == depth[rootN2]) {
                    depth[rootN1]++; // link between rootN1 and rootN2
                }
                numNodes[rootN1] += numNodesN2;
                superRoot = rootN1;
            }
            else {
                int numNodesN1 = numNodes[rootN1];
                nodeParent[rootN1] = nodeParent[rootN2];
                numNodes[rootN2] += numNodesN1;
                superRoot = rootN2;
            }
        }
       
        return numNodes[superRoot];
    }
   
    public static void readRelations(BufferedReader br, BufferedWriter bw, int numRelations) throws NumberFormatException, IOException {
        int count = 1;
        for (int j = 0; j < numRelations; j++) {
            String line = br.readLine();
            String[] names = line.split(" ");
           
            String name1 = names[0];
            String name2 = names[1];
           
            if (!map.containsKey(name1)) {
                map.put(name1, count++);
            }
            if (!map.containsKey(name2)) {
                map.put(name2, count++);
            }
           
            bw.write(union(map.get(name1), map.get(name2))+"\n");
        }
    }
   
    public static void initArrays(int maxNumPeople) {
        for (int j = 1; j <= maxNumPeople; j++) {
            nodeParent[j] = j;
            depth[j] = 0;
            numNodes[j] = 1;
        }
    }
   
    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 = Integer.parseInt(br.readLine());
        for (int i = 0; i < numCases; i++) {
            int numRelations = Integer.parseInt(br.readLine());
            int maxNumPeople = numRelations*2;
           
            nodeParent = new int[maxNumPeople+1]; // numRelations*2+1 = num possible of people
            depth = new int[maxNumPeople+1];
            numNodes = new int[maxNumPeople+1];
           
            initArrays(maxNumPeople);
           
            readRelations(br, bw, numRelations);
           
            map.clear();
        }
       
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}