2685. Count the Number of Complete Components

MediumView on LeetCode

Depth-First Search Breadth-First Search Union Find Graph

Time: O(n + E)

Space: O(n)

Problem Overview

Count connected components in an undirected graph given edges.

Intuition

Count connected components in an undirected graph given edges. Union-Find merges endpoints; number of distinct roots after all unions is the answer. Isolated nodes (not in any edge) still count as their own component if included in node count n.

Algorithm

1Initialize parent[i]=i for i in 0..n-1.
2For each edge [u,v]: union(u,v).
3Count distinct find(i) for all i — or decrement component count on successful unions.
4Return component count.

Example Walkthrough

Input: n = 5, edges = [[0,1],[1,2],[3,4]]

1.Component {0,1,2} and {3,4} → 2 components.

Output: 2

Common Pitfalls

•Nodes with no edges are still components if 0..n-1 all exist.
•Path compression in find speeds large graphs.
•Undirected — union(a,b) once per edge.

2685.cs

// Approach: DFS each component; complete if edge count = k*(k-1)/2 for k nodes.
// Time: O(n + E) Space: O(n)

public class Solution
{
    public int CountCompleteComponents(int n, int[][] edges)
    {
        var adjList = new List<List<int>>();

        for (int i = 0; i < n; i++)
            adjList.Add(new List<int>());

        foreach (int[] edge in edges)
        {
            int u = edge[0];
            int v = edge[1];
            adjList[u].Add(v);
            adjList[v].Add(u);
        }

        int[] vis = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (vis[i] == 0)
            {
                var temp = new List<int>();
                int e = 0;
                DFS(i, adjList, vis, temp, ref e);
                int v = temp.Count;

                if (v * (v - 1) == e)
                    ans++;
            }
        }

        return ans;
    }

    private void DFS(int node, List<List<int>> adjList, int[] vis, List<int> temp, ref int edges)
    {
        vis[node] = 1;
        edges += adjList[node].Count;
        temp.Add(node);

        foreach (int adjNode in adjList[node])
        {
            if (vis[adjNode] == 0)
                DFS(adjNode, adjList, vis, temp, ref edges);
        }
    }
}

Was this solution helpful?