[Spoj] FOXLINGS – Foxlings

Problem statement is here: http://www.spoj.com/problems/FOXLINGS/

The problem can be solved either by repeated BFS after constructing a graph or by using a disjoint set. Disjoint set would be the fastest way and probably the only way to not get TLE  🙂 . Also, a map instead of array would be required to optimize in case you plan to use Java since N has max value of 10^9. One minor optimization would help the case which is to initialize the nodes just before the union step. Code is below:

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

/**
 * author: www.shankhs.com
 */
public class Main {
    private static BufferedReader br;
    static int count;

    static class Node {
        int data;
        Node parent;
        int rank;
    }

    private static Map<Integer, Node> tree;

    private static void makeSet(int data) {
        Node node = new Node();
        node.data = data;
        node.parent = node;
        node.rank = 0;
        tree.put(data, node);
    }

    private static boolean union(int x, int y) {
        Node node1 = tree.get(x);
        Node node2 = tree.get(y);

        Node parent1 = findSet(node1);
        Node parent2 = findSet(node2);

        if (parent1.data == parent2.data) {
            return false;
        }

        if (parent1.rank >= parent2.rank) {
            parent1.rank = parent1.rank == parent2.rank ? parent1.rank + 1 : parent1.rank;
            parent2.parent = parent1;
        } else {
            parent1.parent = parent2;
        }
        count--;
        return true;
    }

    private static int findSet(int data) {
        return findSet(tree.get(data)).data;
    }

    private static Node findSet(Node node) {
        Node parent = node.parent;
        if (parent == node) {
            return parent;
        }
        parent = findSet(parent);
        return parent;
    }


    public static void main(String[] args) throws Exception {
        tree = new HashMap<>();

        br = new BufferedReader(new InputStreamReader(System.in));
        String[] ins = br.readLine().split(" ");
        int n = Integer.valueOf(ins[0]);
        int m = Integer.valueOf(ins[1]);

        count = n;

        for (int i = 0; i < m; i++) {
            String[] rships = br.readLine().split(" ");
            int foxling1 = Integer.valueOf(rships[0]);
            int foxling2 = Integer.valueOf(rships[1]);
            if (!tree.containsKey(foxling1)) {
                makeSet(foxling1);
            }
            if (!tree.containsKey(foxling2)) {
                makeSet(foxling2);
            }
            union(foxling1, foxling2);
        }

        System.out.println(count);

    }
}