原题链接在这里：https://leetcode.com/problems/number-of-connected-components-in-an-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.
Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
题解：
使用一维UnionFind.
Time Complexity: O(elogn). e是edges数目. Space: O(n).
AC Java:
1 public class Solution { 2 public int countComponents(int n, int[][] edges) { 3 if(n < 1){ 4 return 0; 5 } 6 UnionFind forest = new UnionFind(n); 7 for(int [] edge : edges){ 8 if(!forest.find(edge[0], edge[1])){ 9 forest.union(edge[0],edge[1]); 10 } 11 } 12 return forest.size(); 13 } 14 } 15 16 class UnionFind{ 17 private int n, count; 18 private int [] parent; 19 private int [] size; 20 21 public UnionFind(int n){ 22 this.n = n; 23 this.count = n; 24 parent = new int[n+1]; 25 size = new int[n+1]; 26 for(int i = 1; i<parent.length; i++){ 27 parent[i] = i; 28 } 29 for(int i = 1; i<size.length; i++){ 30 size[i] = 1; 31 } 32 } 33 34 private int getIndex(int i){ 35 return i+1; 36 } 37 38 public int getParent(int i){ 39 return parent[getIndex(i)]; 40 } 41 42 public int size(){ 43 return this.count; 44 } 45 46 public boolean find(int i, int j){ 47 return root(i) == root(j); 48 } 49 50 public int root(int i){ 51 if(parent[i] == 0){ 52 return i; 53 } 54 while(i != parent[i]){ 55 parent[i] = parent[parent[i]]; 56 i = parent[i]; 57 } 58 return i; 59 } 60 61 public void union(int p, int q){ 62 int i = root(p); 63 int j = root(q); 64 if(size[i] < size[j]){ 65 parent[i] = j; 66 size[j] += size[i]; 67 }else{ 68 parent[j] = i; 69 size[i] += size[j]; 70 } 71 count--; 72 } 73 }
也可以使用BFS, DFS.
Time Complexity: O(en), 建graph用O(en), BFS, DFS 用 O(n+e). Space: O(n + e).
1 public class Solution { 2 public int countComponents(int n, int[][] edges) { 3 List<List<Integer>> graph = new ArrayList<List<Integer>>(); 4 for(int i = 0; i<n; i++){ 5 graph.add(new ArrayList<Integer>()); 6 } 7 for(int [] edge : edges){ 8 graph.get(edge[0]).add(edge[1]); 9 graph.get(edge[1]).add(edge[0]); 10 } 11 HashSet<Integer> visited = new HashSet<Integer>(); 12 int count = 0; 13 for(int i = 0; i<n; i++){ 14 if(!visited.contains(i)){ 15 //Method 1 BFS 16 //bfs(graph, i, visited); 17 18 //Mehod 2 DFS 19 dfs(graph, i, visited); 20 count++; 21 } 22 } 23 return count; 24 } 25 26 private void bfs(List<List<Integer>> graph, int i, HashSet<Integer> visited){ 27 LinkedList<Integer> que = new LinkedList<Integer>(); 28 visited.add(i); 29 que.add(i); 30 while(!que.isEmpty()){ 31 int cur = que.poll(); 32 List<Integer> neighbours = graph.get(cur); 33 for(int neighbour : neighbours){ 34 if(!visited.contains(neighbour)){ 35 visited.add(neighbour); 36 que.add(neighbour); 37 } 38 } 39 } 40 } 41 42 private void dfs(List<List<Integer>> graph, int i, HashSet<Integer> visited){ 43 visited.add(i); 44 for(int neighbour : graph.get(i)){ 45 if(!visited.contains(neighbour)){ 46 visited.add(neighbour); 47 dfs(graph, neighbour, visited); 48 } 49 } 50 } 51 }
LeetCode Number of Connected Components in an Undirected Graph
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/5247187.html