💬 Discord
Sign In
NeetCode #582LC-323MediumGraphsBlind 75NC 150NC 250NC Algo100
← Back to All Problems

#582 · #323 · Number of Connected Components in an Undirected Graph(无向图中连通分量的数目)

📌 Problem Statement & Constraints

You are given n nodes labelled 0..n-1 and a list of undirected edges. Return the number of connected components. Constraints: 1 <= n <= 2000, 0 <= edges.length <= 5000.

💡 Core Algorithmic Approaches

  1. Union-find with a component counter: start at n components and decrement on every successful union.
  2. A union is successful when the two endpoints have different roots.
  3. The final count is the answer.
  4. A DFS/BFS over the adjacency list counting traversals is an equally good alternative.

💻 Benchmark Python3 Implementation

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        count = n
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra != rb:                   # merging two distinct components
                parent[ra] = rb
                count -= 1
        return count

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(V + E * alpha(V)): effectively linear.
💾 Space Complexity
O(V) for the parent array.

⚠️ Interview Pitfalls & Follow-ups

  • Counting edges instead of merges: only successful merges reduce the component count.
  • Unioning when the roots are equal: that would over-decrement the count.
  • Using a DFS without a visited set: nodes would be revisited.
  • Assuming the graph is connected: the whole point is to count the components.