[Spoj] FRNDCIRC – Friend Circle

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

This problem can be solved using disjoint set data structure. What makes this problem difficult and even more so for Java programmers is the strict time limit. To solve it in Java, clever (buffered) input output is required.

Try to solve it yourself before looking at the solution.

 

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

public class Main {

    private static class Node {
        String data;
        Node parent;
        int childCount;
        int rank;
    }
    private static BufferedReader br;
    private static Map<String, Node> tree;
    static OutputStream outputStream = System.out;
    static OutputWriter out = new OutputWriter(outputStream);

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.valueOf(br.readLine());
        while(t-->0) {
            tree = new HashMap<>();
            int n = Integer.valueOf(br.readLine());
            while(n-->0) {
                String[] friends = br.readLine().split(" ");
                if(!tree.containsKey(friends[0])) {
                    makeSet(friends[0]);
                }
                if(!tree.containsKey(friends[1])) {
                    makeSet(friends[1]);
                }
                int maxCount = union(friends);
                out.println(maxCount);
            }
        }
        out.close();
    }

    private static int union(String[] friends) {
        Node f0 = tree.get(friends[0]);
        Node f1 = tree.get(friends[1]);

        Node p0 = findSet(f0);
        Node p1 = findSet(f1);
        if(p0==p1)  return p0.childCount;

        if(p0.rank>=p1.rank) {
            p1.parent = p0;
            p0.childCount += p1.childCount;
            if(p1.rank==p0.rank) {
                p0.rank++;
            }
            return p0.childCount;
        } else {
            p0.parent = p1;
            p1.childCount+=p0.childCount;
            return p1.childCount;
        }
    }

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

    private static void makeSet(String friend) {
        Node node = new Node();
        node.data = friend;
        node.parent = node;
        node.childCount=1;
        node.rank = 1;
        tree.put(friend, node);
    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
                    outputStream)));
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }
}