[Algorithm] Union Find Applications

1. Kruskal Algorithm Minimal Spanning Tree
1. Greedy Algorithm, sort all edges.
2. Initialize each node as a set.
3. Start from the smallest edge, union if they are not in the same set.
2. Check Loop of Undirected Graph
3. Check connection in undirected graph
4. Tarjan's off-line lowest common ancestors algorithm
1. Offline algorithm. All queries know in advance
2. For tree with n node and m queries. We have O(n + m) running time.
3. Request (u, v) is answered when u is visited, v is the current visiting node. or vice versa.
4. https://gist.github.com/caot/696fb3d762af0d2340c1
5. Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class TarjanOfflineLCA {

  void LCA(Node u) {
    MakeSet(u);
    Find(u).ancestor = u;
    for (Node v : u.children()) {
      LCA(v);
      Union(u, v);
      Find(u).ancestor = u;
    }
    u.colour = Node.black;
    Node v;
    for (Pair uv : P.pair()) {
      u = uv.u();
      v = uv.v();
      if (v.colour == Node.black
          && u != null && v != null
          && Find(u) == Find(v)     // required, but algorithm [3th Ed. p584] doesn't have it.
          ) {
        System.out.println("Tarjan's Lowest Common Ancestor of {" + u.data
            + ", " + v.data + "}: " + Find(v).ancestor.data);
      }
    }
  }

  

1. The basic idea is in infact DFS
2. Recursive DFS travels from all the way from bottom to up, left to right.
3. A node is marked as black if all its children are visited (marked as black)
4. Black means, in query Ancester(u, v), if u is marked as black, the ancester pointer is pointed to the right place ( right place = exacted the common ancestor of v)
5. The property of 3 is guaranteed by the nature of DFS. 
5. HDU-1213 How many tables
1. Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers. One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table. For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
6.