LeetCode 2685: Count the Number of Complete Components Solution

Master LeetCode problem 2685 (Count the Number of Complete Components), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2685. Count the Number of Complete Components

Medium

Depth-First Search Breadth-First Search Union Find Graph

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2685 (Count the Number of Complete Components)?

This page provides optimized solutions for LeetCode problem 2685 (Count the Number of Complete Components) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2685 (Count the Number of Complete Components)?

The time complexity for LeetCode 2685 (Count the Number of Complete Components) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2685 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2685 in Java, C++, or Python.

Back to LeetCode Solutions