323. 无向图中连通分量的数目

题目

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

题解

深度优先遍历

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countComponents = function(n, edges) {
  // 邻接表
  let adj = new Array(n);
  for (let i = 0; i < n; i++) {
    adj[i] = [];
  }

  // 把边的信息加入到邻接表中
  for (let e of edges) {
    // 无向图 双向添加
    adj[e[0]].push(e[1]);
    adj[e[1]].push(e[0]);
  }
  let c = 0;
  let vis = new Array(n).fill(false);
  for (let i = 0; i < n; i++) {
    if (!vis[i]) {
      // 深度遍历 标记该点的所有连通点
      dfs(adj, i, vis);
      c++;
    }
  }
  return c;
};

function dfs(adj, u, vis) {
  vis[u] = true;
  let s = adj[u];
  for (let x of s) {
    if (!vis[x]) dfs(adj, x, vis);
  }
}