LeetCode 2685: Count the Number of Complete Components
Problem Description
Explanation
To solve this problem, we can use a union-find algorithm. We will initially consider each vertex as its own component. Then, for each edge, we will union the components to which the vertices of the edge belong. Finally, we will count the number of complete components by checking if all vertices in a component are connected to each other.
Steps:
- Initialize a parent array where each vertex is its own parent initially.
- Iterate through the edges and for each edge, union the components of the two vertices.
- After processing all edges, count the number of complete components by checking if all vertices in a component have the same parent.
Time Complexity: O(n + edges) where n is the number of vertices and edges is the number of edges. Space Complexity: O(n) for the parent array.
Solutions
class Solution {
public int countComponents(int n, int[][] edges) {
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for (int[] edge : edges) {
int parent1 = findParent(parent, edge[0]);
int parent2 = findParent(parent, edge[1]);
if (parent1 != parent2) {
parent[parent1] = parent2;
}
}
int count = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == i) {
count++;
}
}
return count;
}
private int findParent(int[] parent, int vertex) {
while (parent[vertex] != vertex) {
parent[vertex] = parent[parent[vertex]];
vertex = parent[vertex];
}
return vertex;
}
}Loading editor...