2685. Count the Number of Complete Components LeetCode Solution
In this guide, you will get 2685. Count the Number of Complete Components LeetCode Solution with the best time and space complexity. The solution to Count the Number of Complete Components problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count the Number of Complete Components
You are given an integer n. There is an undirected graph with n vertices, numbered from 0 to n – 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting vertices ai and bi.
Return the number of complete connected components of the graph.
A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.
A connected component is said to be complete if there exists an edge between every pair of its vertices.
Example 1:
Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
Output: 3
Explanation: From the picture above, one can see that all of the components of this graph are complete.
Example 2:
Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
Output: 1
Explanation: The component containing vertices 0, 1, and 2 is complete since there is an edge between every pair of two vertices. On the other hand, the component containing vertices 3, 4, and 5 is not complete since there is no edge between vertices 4 and 5. Thus, the number of complete components in this graph is 1.
1 <= n <= 50
0 <= edges.length <= n * (n – 1) / 2
edges[i].length == 2
0 <= ai, bi <= n – 1
ai != bi
There are no repeated edges.
Complexity Analysis
Time Complexity: O(|V| + |E|)
Space Complexity: O(|V| + |E|)
2685. Count the Number of Complete Components LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), rank(n), nodeCount(n, 1), edgeCount(n) {
iota(id.begin(), id.end(), 0);
}
void unionByRank(int u, int v) {
const int i = find(u);
const int j = find(v);
++edgeCount[i];
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
edgeCount[j] += edgeCount[i];
nodeCount[j] += nodeCount[i];
} else if (rank[i] > rank[j]) {
id[j] = i;
edgeCount[i] += edgeCount[j];
nodeCount[i] += nodeCount[j];
} else {
id[i] = j;
edgeCount[j] += edgeCount[i];
nodeCount[j] += nodeCount[i];
++rank[j];
}
}
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
bool isComplete(int u) {
return nodeCount[u] * (nodeCount[u] - 1) / 2 == edgeCount[u];
}
private:
vector<int> id;
vector<int> rank;
vector<int> nodeCount;
vector<int> edgeCount;
};
class Solution {
public:
int countCompleteComponents(int n, vector<vector<int>>& edges) {
int ans = 0;
UnionFind uf(n);
unordered_set<int> parents;
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
uf.unionByRank(u, v);
}
for (int i = 0; i < n; ++i) {
const int parent = uf.find(i);
if (parents.insert(parent).second && uf.isComplete(parent))
++ans;
}
return ans;
}
}; /* code provided by PROGIEZ */
2685. Count the Number of Complete Components LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
nodeCount = new int[n];
edgeCount = new int[n];
for (int i = 0; i < n; ++i) {
id[i] = i;
nodeCount[i] = 1;
}
}
public void unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
++edgeCount[i];
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
edgeCount[j] += edgeCount[i];
nodeCount[j] += nodeCount[i];
} else if (rank[i] > rank[j]) {
id[j] = i;
edgeCount[i] += edgeCount[j];
nodeCount[i] += nodeCount[j];
} else {
id[i] = j;
edgeCount[j] += edgeCount[i];
nodeCount[j] += nodeCount[i];
++rank[j];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
public boolean isComplete(int u) {
return nodeCount[u] * (nodeCount[u] - 1) / 2 == edgeCount[u];
}
private int[] id;
private int[] rank;
private int[] nodeCount;
private int[] edgeCount;
}
class Solution {
public int countCompleteComponents(int n, int[][] edges) {
int ans = 0;
UnionFind uf = new UnionFind(n);
Set<Integer> parents = new HashSet<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
uf.unionByRank(u, v);
}
for (int i = 0; i < n; ++i) {
final int parent = uf.find(i);
if (parents.add(parent) && uf.isComplete(parent))
++ans;
}
return ans;
}
} // code provided by PROGIEZ
2685. Count the Number of Complete Components LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
self.nodeCount = [1] * n
self.edgeCount = [0] * n
def unionByRank(self, u: int, v: int) -> None:
i = self.find(u)
j = self.find(v)
self.edgeCount[i] += 1
if i == j:
return
if self.rank[i] < self.rank[j]:
self.id[i] = j
self.edgeCount[j] += self.edgeCount[i]
self.nodeCount[j] += self.nodeCount[i]
elif self.rank[i] > self.rank[j]:
self.id[j] = i
self.edgeCount[i] += self.edgeCount[j]
self.nodeCount[i] += self.nodeCount[j]
else:
self.id[i] = j
self.edgeCount[j] += self.edgeCount[i]
self.nodeCount[j] += self.nodeCount[i]
self.rank[j] += 1
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
def isComplete(self, u):
return self.nodeCount[u] * (self.nodeCount[u] - 1) // 2 == self.edgeCount[u]
class Solution:
def countCompleteComponents(self, n: int, edges: list[list[int]]) -> int:
ans = 0
uf = UnionFind(n)
parents = set()
for u, v in edges:
uf.unionByRank(u, v)
for i in range(n):
parent = uf.find(i)
if parent not in parents and uf.isComplete(parent):
ans += 1
parents.add(parent)
return ans # code by PROGIEZ
