• ㊗️
• 大家
• offer
• 多多！

## Problem

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.

## Code

DFS

class Solution {
public int countComponents(int n, int[][] edges) {
boolean[] visited = new boolean[n];
int count = 0;

for (int i = 0; i < n; i++) {
if (!visited[i]) {
helper(edges, visited, i);
count++;
}
}
return count;
}

private void helper(int[][] edges, boolean[] visited, int node) {
if (visited[node]) return;
visited[node] = true;
for (int[] edge : edges) {
int x = edge[0];
int y = edge[1];
if (x == node && !visited[y]) {
helper(edges, visited, y);
}

if (y == node && !visited[x]) {
helper(edges, visited, x);
}
}
}
}


BFS

class Solution {
public int countComponents(int n, int[][] edges) {
boolean[] visited = new boolean[n];

int count = 0;

for (int i = 0; i < n; i++) {
if (!visited[i]) {
queue.offer(i);
while (!queue.isEmpty()) {
int curr = queue.poll();
visited[curr] = true;
for (int[] edge : edges) {
int x = edge[0];
int y = edge[1];
if (x == curr && !visited[y]) {
queue.offer(y);
}

if (y == curr && !visited[x]) {
queue.offer(x);
}
}
}
count++;
}
}
return count;
}
}


union find

class Solution {
public class UnionFind {
int[] parents;
int[] ranks;
int groupNum = 0;

// one dimension
public UnionFind(int n) {
parents = new int[n];
ranks = new int[n];

for (int i = 0; i < n; i++) {
parents[i] = i;
ranks[i] = 1;
}

groupNum = n;
}

public boolean union(int x, int y) {
int xParent = find(x);
int yParent = find(y);
// same parent
if (xParent == yParent) return false;
// different parent
groupNum--;
if (ranks[xParent] > ranks[yParent]) {
parents[yParent] = xParent;
} else if (ranks[xParent] < ranks[yParent]) {
parents[xParent] = yParent;
} else {
parents[yParent] = xParent;
ranks[xParent]++;
}

return true;
}

public int find(int node) {
while (node != parents[node]) {
int parentNode = parents[parents[node]];

parents[node] = parentNode;
node = parentNode;
}

return node;
}

public int getGroupNum() {
return groupNum;
}
}

public int countComponents(int n, int[][] edges) {
UnionFind node = new UnionFind(n);

for(int[] edge : edges){
node.union(edge[0], edge[1]);
}

return node.getGroupNum();
}
}