Using Union-Find - Algorithm

Methods:
- find, union, isConnected, findCount
- highestRank, maxUnion
- find grouped ids

Group Contacts | tech::interview
LintCode 432 - Find the Weak Connected Component in the Directed Graph

Google – Manager Peer Problem
Design a data structure to support following functions:
1. setManager(A, B) sets A as a direct manager of B
2. setPeer(A, B) sets A as a colleague of B. After that, A and B will have the same direct Manager.
3. query(A, B) returns if A is in the management chain of B.
Every person only has 1 direct manager.
- union-find but don't do path compression
- Tree + Hash Table
Map nodeMap = new HashMap<>();
private class TNode {
  int val;
  TNode parent;
  List neighbors;
}

LeetCode 323 - Number of Connected Components in an Undirected Graph

LeetCode 547 - Friend Circles


LeetCode 305 - Number of Islands II
Given a list of positions to operate, count the number of islands after each addLand operation

LeetCode 261 - Graph Valid Tree
- BFS
- UF

LeetCode 128 - Longest Consecutive Sequence
- https://discuss.leetcode.com/topic/6148/my-really-simple-java-o-n-solution-accepted
- https://discuss.leetcode.com/topic/17980/another-accepted-java-o-n-solution
- Union Find
- highestRank, maxUnion

LeetCode - Surrounded Regions
- Matrix: process all boundaries first
- Flood fill
X. BFS, DFS
X. Using Union-Find
  1.     public void solve(char[][] board) {  
  2.         if (board == null || board.length == 0 || board[0].length == 0)  
  3.             return;  
  4.         int rows = board.length, cols = board[0].length;  
  5.         int oRoot = rows * cols;  
  6.         initUnionFind(rows * cols);  
  7.         for (int i = 0; i < rows; i++) {  
  8.             for (int j = 0; j < cols; j++) {  
  9.                 if (board[i][j] == 'X'continue;  
  10.                 int curr = i * cols + j;  
  11.                 if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {  
  12.                     union(curr, oRoot);  
  13.                 } else {  
  14.                     if (j + 1 < cols && board[i][j + 1] == 'O')  
  15.                         union(curr, i * cols + j + 1);  
  16.                     if (j - 1 >= 0 && board[i][j - 1] == 'O')  
  17.                         union(curr, i * cols + j - 1);  
  18.                     if (i + 1 < rows && board[i + 1][j] == 'O')  
  19.                         union(curr, (i + 1) * cols + j);  
  20.                     if (i - 1 >= 0 && board[i - 1][j] == 'O')  
  21.                         union(curr, (i - 1) * cols + j);  
  22.                 }  
  23.             }  
  24.         }  
  25.         for (int i = 0; i < rows; i++) {  
  26.             for (int j = 0; j < cols; j++) {  
  27.                 if (board[i][j] == 'O' && find(i * cols + j) != oRoot) {  
  28.                     board[i][j] = 'X';  
  29.                 }  
  30.             }  
  31.         }  
  32.     }  
  33.     int[] s;  
  34.     int[] rank;  
  35.     private void initUnionFind(int n) {  
  36.         s = new int[n + 1];  
  37.         rank = new int[n + 1];  
  38.         for (int i = 0; i <= n; i++)  
  39.             s[i] = i;  
  40.         rank[n] = n + 1;  
  41.     }  
  42.     private int find(int p) {  
  43.         if (s[p] == p) return p;  
  44.         else return s[p] = find(s[p]);  
  45.     }  
  46.     private void union(int p, int q) {  
  47.         int pRoot = find(p), qRoot = find(q);  
  48.         if (pRoot == qRoot) return;  
  49.         if (rank[pRoot] < rank[qRoot]) {  
  50.             s[pRoot] = qRoot;  
  51.         } else {  
  52.             if (rank[pRoot] == rank[qRoot])  
  53.                 rank[pRoot]++;  
  54.             s[qRoot] = pRoot;  
  55.         }  
  56.     }  


Union-Find implementation
- Using HahsMap
51 class UnionFind{
52     
53     //HashMap maintaining key - > value (child -> parent) relationship
54     HashMap parent;
55     public UnionFind(HashSet hs){
56         parent = new HashMap();
57         for(int i : hs){
58             parent.put(i, i);
59         }
60     }
61     
62     public int root(int i){
63         while(i != parent.get(i)){
64             parent.put(i, parent.get(parent.get(i)));
65             i = parent.get(i);
66         }
67         return i;
68     }
69     
70     public void union(int i, int j){
71         int p = root(i);
72         int q = root(j);
73         if(p != q){
74             parent.put(p, q);
75         }
76     }
Using Array
    class UnionFind {
        private int count = 0;
        private int[] parent, rank;
        
        public UnionFind(int n) {
            count = n;
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        
        public int find(int p) {
         while (p != parent[p]) {
                parent[p] = parent[parent[p]];    // path compression by halving
                p = parent[p];
            }
            return p;
        }
        
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            if (rank[rootQ] > rank[rootP]) {
                parent[rootP] = rootQ;
            }
            else {
                parent[rootQ] = rootP;
                if (rank[rootP] == rank[rootQ]) {
                    rank[rootP]++;
                }
            }
            count--;
        }
        
        public int count() {
            return count;
        }


Post a Comment

Labels

Java (159) Lucene-Solr (110) All (58) Interview (58) J2SE (53) Algorithm (43) Soft Skills (36) Eclipse (34) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (15) Defects (14) Text Mining (14) J2EE (13) Network (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Dynamic Languages (8) Http Client (8) Maven (8) Security (8) Trouble Shooting (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Problem Solving (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) IDE (5) Lesson Learned (5) Programmer Skills (5) System Design (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Python (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Troubleshooting (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts