# [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.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<>();

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);

}
}
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.