876294. Connected Components in an Undirected Graph
Connected Components in an Undirected Graph
Slug: connected-components-in-an-undirected-graph
Difficulty: Medium
Id: 876294
Topic Tags: Graph, union-find, DFS, BFS
Company Tags: None
Summary
In this problem, we are given an undirected graph represented as an adjacency list. Our task is to find the number of connected components in the graph. A connected component is a subgraph where all nodes are reachable from each other. We can use either depth-first search (DFS) or breadth-first search (BFS) to solve this problem.
Detailed Explanation
To solve this problem, we will create a union-find data structure and iterate through the adjacency list of the graph. For each edge in the graph, if the two nodes are not connected, we merge them into the same connected component. This approach ensures that all nodes in the same connected component are merged together.
Here is a step-by-step breakdown of the solution:
- Initialize an empty union-find data structure.
- Iterate through the adjacency list of the graph.
- For each edge in the graph, check if the two nodes are not connected using the union-find data structure.
- If the nodes are not connected, merge them into the same connected component.
- Repeat steps 2-4 until all edges have been processed.
- The number of connected components is equal to the number of distinct roots in the union-find data structure.
Time complexity: O(V + E), where V is the number of vertices and E is the number of edges, since we iterate through the adjacency list once. Space complexity: O(V), since we need to store the union-find data structure.
Optimized Solutions
Java
class Solution {
public int findConnectedComponents(int[][] graph) {
if (graph == null || graph.length == 0) return 0;
int connectedComponents = 0;
boolean[] visited = new boolean[graph.length];
for (int i = 0; i < graph.length; i++) {
if (!visited[i]) {
dfs(graph, i, visited);
connectedComponents++;
}
}
return connectedComponents;
}
private void dfs(int[][] graph, int node, boolean[] visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited);
}
}
}
}