(UVA) Graph Connectivity - Solution 1

I used Union-Find to solve this problem.


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

class Main {
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int count() {
        int[] v = new int[nodeParent.length];
        for (int i = 0; i < nodeParent.length; i++) {
            v[root(nodeParent[i])]++;  
        }
       
        int c = 0;
        for (int i = 0; i < v.length; i++) {
            if (v[i] != 0) {
                c++;
            }
        }
       
        return c;
    }
   
    public static int root(int n) {
        while (nodeParent[n] != n) {
            n = nodeParent[n];
        }
       
        return n;
    }
   
    public static void union(int n1, int n2) {
        int rootN1 = root(n1);
        int rootN2 = root(n2);
       
        if (rootN1 != rootN2) {
            if (depth[rootN1] >= depth[rootN2]) {
                nodeParent[rootN2] = nodeParent[rootN1];
                if (depth[rootN1] == depth[rootN2]) {
                    depth[rootN1]++;
                }
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        int numCases = Integer.parseInt(line);
        line = br.readLine(); // blank line
        for (int i = 0; i < numCases; i++) {
            if (i > 0) {
                System.out.println();
            }
           
            String max = br.readLine();
            int numNodes = max.charAt(0)-'A'+1;
            nodeParent = new int[numNodes];
            depth = new int[numNodes];
            for (int j = 0; j < numNodes; j++) {
                nodeParent[j] = j;
                depth[j] = 0;
            }
           
            line = br.readLine();
            while (!line.equals("")) {
                char c1 = line.charAt(0);
                char c2 = line.charAt(1);
                union(c1-'A', c2-'A');
               
                line = br.readLine(); 
                if (line == null) {
                    break;
                }             
            }
           
            System.out.println(count());
        }
                                               
        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