323.Number-of-Connected-Components-in-an-Undirected-Graph

323. Number of Connected Components in an Undirected Graph

题目地址

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:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2
Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  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.

代码

Approach #1 DFS

class Solution {
  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)) {
        dfs(i, map, visited);
        count++;
      }
    }
    return count;
  }

  private void dfs(int i, Map<Integer, List<Integer>> map, Set<Integer> visited) {
    for (int j : map.get(i)) {
      if (visited.add(j)) {
        dfs(j, map, visited);
      }
    }
  }
}