LeetCode323.NumberofConnectedComponentsinanUndirectedGraph

原题链接在这里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数目. Find, O(logn). Union, O(1).

Space: O(n).

AC Java:

1 class Solution { 2 public int countComponents(int n, int[][] edges) { 3 if(n < 0){ 4 return 0; 5 } 6 7 UnionFind uf new UnionFind(n); 8 for(int [] edge : edges){ 9 if(!uf.find(edge[0], edge[1])){10 uf.union(edge[0], edge[1]);11 }12 }13 14 return uf.size();15 }16 }17 18 class UnionFind{19 private int count;20 private int [] parent;21 private int [] size;22 23 public UnionFind(int n){24 this.count n;25 parent new int[n];26 size new int[n];27 for(int i 0; i size[rootJ]){50 parent[rootJ] rootI;51 size[rootI] size[j];52 }else{53 parent[rootI] rootJ;54 size[rootJ] size[rootI];55 }56 57 this.count--;58 }59 60 public int size(){61 return this.count;62 }63 }

也可以使用BFS, DFS.

Time Complexity: O(ne), 建graph用O(ne), BFS, DFS 用 O(ne). Space: O(n e).

1 public class Solution { 2 public int countComponents(int n, int[][] edges) { 3 List graph new ArrayList(); 4 for(int i 0; i graph, int i, HashSet visited){26 LinkedList que new LinkedList();27 visited.add(i);28 que.add(i);29 while(!que.isEmpty()){30 int cur que.poll();31 List neighbours graph.get(cur);32 for(int neighbour : neighbours){33 if(!visited.contains(neighbour)){34 que.add(neighbour);35 visited.add(neighbour);36 }37 }38 }39 }40 41 public void dfs(List graph, int i, HashSet visited){42 visited.add(i);43 for(int neighbour : graph.get(i)){44 if(!visited.contains(neighbour)){45 dfs(graph, neighbour, visited);46 }47 }48 }49 }

跟上Find the Weak Connected Component in the Directed Graph, Number of Islands II.

转:https://www.cnblogs.com/Dylan-Java-NYC/p/5247187.html