LeetCode 323 - Number of Connected Components in an Undirected Graph


http://segmentfault.com/a/1190000004224298
Related: Lintcode 431 - Find the Connected Component in the Undirected Graph
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
    0          3
    |          |
    1 --- 2    4
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.
Example 2:
    0           4
    |           |
    1 --- 2 --- 3
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.
 2     public int countComponents(int n, int[][] edges) {
 3         unionFind uf = new unionFind(n);
 4         for (int[] edge : edges) {
 5             if (!uf.isConnected(edge[0], edge[1])) {
 6                 uf.union(edge[0], edge[1]);
 7             }
 8         }
 9         return uf.findCount();
10     }
11     
12     public class unionFind{
13             int[] ids;
14             int count;
15             
16             public unionFind(int num) {
17                 this.ids = new int[num];
18                 for (int i=0; i<num; i++) {
19                     ids[i] = i;
20                 }
21                 this.count = num;
22             }
23             
24             public int find(int i) {
25                 return ids[i];
26             }
27             
28             public void union(int i1, int i2) {
29                 int id1 = find(i1);
30                 int id2 = find(i2);
31                 if (id1 != id2) {
32                     for (int i=0; i<ids.length; i++) {
33                         if (ids[i] == id2) {
34                             ids[i] = id1;
35                         }
36                     }
37                     count--;
38                 }
39             }
40             
41             public boolean isConnected(int i1, int i2) {
42                 return find(i1)==find(i2);
43             }
44             
45             public int findCount() {
46                 return count;
47             }
48         }

典型且很基础的union find题。用一个数组记录各个数字的父节点,然后遍历图,对edge中两个端点做union。最后扫一遍数组,找到根节点个数即可。
time: O(m*h), space: O(n), m表示edge的数量。
    public int countComponents(int n, int[][] edges) {
        int[] id = new int[n];
        
        // 初始化
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
        
        // union
        for (int[] edge : edges) {              
            int i = root(id, edge[0]);
            int j = root(id, edge[1]);
            id[i] = j;
        }
        
        // 统计根节点个数
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (id[i] == i)
                count++;
        }
        return count;
    }
    
    // 找根节点
    public int root(int[] id, int i) {
        while (i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }
https://leetcode.com/discuss/76519/similar-to-number-of-islands-ii-with-a-findroot-function
public int countComponents(int n, int[][] edges) {
    int res = n;

    int[] root = new int[n];
    for (int i = 0; i < n; i++) {
        root[i] = i;
    }
    for (int[] pair : edges) {
        int rootX = findRoot(root, pair[0]);
        int rootY = findRoot(root, pair[1]);
        if (rootX != rootY) {
            root[rootY] = rootX;
            res--;
        }
    }
    return res;
}
public int findRoot(int[] root, int i) {
    while (root[i] != i) i = root[i];
    return i;
}
https://leetcode.com/discuss/93661/java-union-find-%26-dfs-%26-bfs-code-very-clean
public int countComponents(int n, int[][] edges) { if (n <= 1) { return n; } int[] roots = new int[n]; for (int i = 0; i < n; i++) { roots[i] = i; } for (int[] edge : edges) { int x = find(roots, edge[0]); int y = find(roots, edge[1]); if (x != y) { roots[x] = y; n--; } } return n; } public int find(int[] roots, int id) { int x = id; while (roots[id] != id) { id = roots[id]; } while (roots[x] != id) { int fa = roots[x]; roots[x] = id; x = fa; } return id; }

With path compression
https://leetcode.com/discuss/76699/java-union-find-%26-path-compression-with-brief-comments
https://leetcode.com/discuss/78217/easy-java-solution-explanation-beats-submissions-union-find
public int countComponents(int n, int[][] edges) { if(n<1) return 0; int[] size = new int[n]; // size of components at every node int[] root = new int[n]; // root of current node for(int i=0; i<n; i++) size[i] = 1; // initialize size to 1 for(int i=0; i<n; i++) root[i] = i; // initialize root to itself for(int[] edge : edges) union(edge[0], edge[1], root, size); // union all edges int count = 0; for(int i=0; i<n; i++) count += (root[i]==i) ? 1 : 0; return count; } private int root(int a, int[] root) { while(a!=root[a]) a = root(root[a], root); // path compression return a; } private void union(int a, int b, int[] root, int[] size) { int roota = root(a, root); int rootb = root(b, root); if(roota==rootb) return; // (a,b) already in same set, return immediately if(size[roota]>size[rootb]) { size[roota] += size[rootb]; // set larger size to sum root[rootb] = roota; // set smaller node to larger node's child } else { size[rootb] += size[roota]; root[roota] = rootb; } }
http://buttercola.blogspot.com/2016/01/leetcode-number-of-connected-components.html
private int[] father;
public int countComponents(int n, int[][] edges) {
    Set<Integer> set = new HashSet<Integer>();
    father = new int[n];
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
    for (int i = 0; i < edges.length; i++) {
         union(edges[i][0], edges[i][1]);
    }
    for (int i = 0; i < n; i++){
        set.add(find(i));
    }
    return set.size();
}
int find(int node) {
    if (father[node] == node) {
        return node;
    }
    father[node] = find(father[node]);
    return father[node];
}
void union(int node1, int node2) {
    father[find(node1)] = find(node2);
}
X. BFS
https://leetcode.com/discuss/93661/java-union-find-%26-dfs-%26-bfs-code-very-clean
public int countComponents(int n, int[][] edges) { if (n <= 1) { return n; } List<List<Integer>> adjList = new ArrayList<List<Integer>>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<Integer>()); } for (int[] edge : edges) { adjList.get(edge[0]).add(edge[1]); adjList.get(edge[1]).add(edge[0]); } boolean[] visited = new boolean[n]; int count = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { count++; Queue<Integer> queue = new LinkedList<Integer>(); queue.offer(i); while (!queue.isEmpty()) { int index = queue.poll(); visited[index] = true; for (int next : adjList.get(index)) { if (!visited[next]) { queue.offer(next); } } } } } return count; }
https://leetcode.com/discuss/85395/standard-bfs-and-dfs-solution-java
public int countComponents(int n, int[][] edges) { List<List<Integer>> graph = new ArrayList<>(); for(int i=0;i<n;i++){ graph.add(new ArrayList<>()); } for(int[] item : edges){ graph.get(item[1]).add(item[0]); graph.get(item[0]).add(item[1]); }// done with building graph HashSet<Integer> visited = new HashSet<>(); int count = 0; for(int i=0;i<n;i++){ if(!visited.contains(i)){ count++; // dfs(i,graph,visited); bfs(graph,i,visited); } } return count; } public void bfs(List<List<Integer>> graph, int i, HashSet<Integer> visited){ Queue<Integer> q = new LinkedList<>(); q.offer(i); visited.add(i); while(!q.isEmpty()){ int curr = q.poll(); for(int neighbor : graph.get(curr)){ if(!visited.contains(neighbor)){ q.offer(neighbor); visited.add(neighbor); } } } } public void dfs(int i, List<List<Integer>> graph, HashSet<Integer> visited){ visited.add(i); for(int num : graph.get(i)){ if(!visited.contains(num)){ dfs(num,graph,visited); } } }
DFS:
https://leetcode.com/discuss/76608/concise-java-dfs-solution
public int countComponents(int n, int[][] edges) { Map<Integer, List<Integer>> graph = new HashMap<>(); for (int i = 0; i < n; i++) { graph.put(i, new ArrayList<Integer>()); } for (int i = 0; i < edges.length; i++) { graph.get(edges[i][0]).add(edges[i][1]); graph.get(edges[i][1]).add(edges[i][0]); } boolean[] visit = new boolean[n]; Arrays.fill(visit, false); int count = 0; for (int i = 0; i < n; i++) { if (!visit[i]) { bfs(i, graph, visit); count++; } } return count; } private void bfs(int i, Map<Integer, List<Integer>> graph, boolean[] visit) { if (visit[i]) { return; } visit[i] = true; List<Integer> neighbors = graph.get(i); for (Integer integer: neighbors) { bfs((int)integer, graph, visit); } }
https://leetcode.com/discuss/93661/java-union-find-%26-dfs-%26-bfs-code-very-clean
-- previous solution is better
public int countComponents(int n, int[][] edges) { if (n <= 1) { return n; } List<List<Integer>> adjList = new ArrayList<List<Integer>>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<Integer>()); } for (int[] edge : edges) { adjList.get(edge[0]).add(edge[1]); adjList.get(edge[1]).add(edge[0]); } boolean[] visited = new boolean[n]; int count = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { count++; dfs(visited, i, adjList); } } return count; } public void dfs(boolean[] visited, int index, List<List<Integer>> adjList) { visited[index] = true; for (int i : adjList.get(index)) { if (!visited[i]) { dfs(visited, i, adjList); } } }
https://leetcode.com/discuss/80671/java-concise-dfs
public int countComponents(int n, int[][] edges) { if (n <= 1) return n; Map<Integer, List<Integer>> map = new HashMap<>(); for (int i = 0; i < n; i++) { map.put(i, new ArrayList<>()); } for (int[] edge : edges) { map.get(edge[0]).add(edge[1]); map.get(edge[1]).add(edge[0]); } Set<Integer> visited = new HashSet<>(); int count = 0; for (int i = 0; i < n; i++) { if (visited.add(i)) { dfsVisit(i, map, visited); count++; } } return count; } private void dfsVisit(int i, Map<Integer, List<Integer>> map, Set<Integer> visited) { for (int j : map.get(i)) { if (visited.add(j)) dfsVisit(j, map, visited); } }
https://discuss.leetcode.com/topic/24/friend-circles/
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if A is friend of B and B is friend of C, then A is also friend of C. A friend circle is a group of students who are directly or indirectly friends.
You are given a N×N − matrix M which consists of characters Y or N. If M[i][j]=Y, then ith and jth students are friends with each other, otherwise not. You have to print the total number of friend circles in the class.
Each element of matrix friends will be Y or N.
Number of rows and columns will be equal in the matrix.
M[i][i]=Y, where 0≤i<N0≤i<N
M[i][j] = M[j][i], where 0≤i<j<N
Example 1
Input:
YYNN
YYYN
NYYN
NNNY
Output: 2
Example 2
Input
YNNNN
NYNNN
NNYNN
NNNYN
NNNNY
Output: 5
Since M[i][j] = M[j][i], it is an undirected graph. Each friend circle can be represented as one connected component in an undirected graph, which translates directly to this problem:
The only difference is in the input format. This is given as a 2D boolean matrix, while the above problem's input is in edge-pairs representation
http://buttercola.blogspot.com/2016/01/leetcode-number-of-connected-components.html

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts