Number of Connected Components

🎯

Number of Connected Components

mediumGRAPHAmazonLinkedInGoogle

Imagine a social network where you want to find how many friend groups exist - groups where everyone is connected directly or indirectly.

💡 This problem asks how many isolated groups exist in a network. Beginners often struggle because they don't see how to traverse the graph efficiently or how to mark visited nodes to avoid counting duplicates.

📋

Problem Statement

Given an undirected graph with n nodes labeled from 0 to n-1 and a list of edges where each edge connects two nodes, return the number of connected components in the graph.

1 ≤ n ≤ 10^50 ≤ edges.length ≤ 10^5edges[i].length == 20 ≤ edges[i][0], edges[i][1] < nNo duplicate edgesNo self-loops

💡

Example

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

Output2

There are two connected components: {0,1,2} and {3,4}.

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

Output1

All nodes are connected forming a single component.

• n = 1, edges = [] → 1 (single node is one component)
• n = 3, edges = [] → 3 (no edges, all nodes isolated)
• n = 4, edges = [[0,1],[2,3]] → 2 (two pairs of connected nodes)
• n = 0, edges = [] → 0 (no nodes means no components)

⚠️

Common Mistakes

Not marking nodes as visited

Infinite loops or counting the same component multiple times

✅ Always mark nodes visited when traversed

Building graph incorrectly (e.g., directed instead of undirected)

Incorrect component counts due to missing edges

✅ Add edges both ways for undirected graphs

Stack overflow in DFS for large graphs

Runtime error due to deep recursion

✅ Increase recursion limit or use iterative DFS/BFS

Incorrect union-find implementation without path compression or rank

Slower performance, possible TLE on large inputs

✅ Implement path compression and union by rank

Not handling isolated nodes (nodes with no edges)

Under-counting connected components

✅ Iterate over all nodes, not just those in edges

🧠

Brute Force (DFS with adjacency list)

💡 This approach introduces the fundamental graph traversal technique (DFS) to explore connected nodes. It is the foundation for understanding graph connectivity.

Intuition

We start from each unvisited node and perform a DFS to mark all nodes reachable from it as visited. Each DFS call corresponds to one connected component.

Algorithm

1. Build an adjacency list from the edges.
2. Initialize a visited set to keep track of visited nodes.
3. Iterate over all nodes; if a node is not visited, perform DFS from it.
4. Each DFS call marks all nodes in that component as visited; increment component count.

💡 The challenge is to realize that each DFS fully explores one connected component, so counting DFS calls equals counting components.

</>

Code

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def countComponents(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    count = 0
    for i in range(n):
        if i not in visited:
            dfs(i)
            count += 1
    return count

# Driver code
if __name__ == '__main__':
    n = 5
    edges = [[0,1],[1,2],[3,4]]
    print(countComponents(n, edges))  # Output: 2

Line Notes

from collections import defaultdictUse defaultdict to simplify adjacency list creation

sys.setrecursionlimit(10**7)Increase recursion limit to avoid stack overflow on large graphs

graph = defaultdict(list)Initialize adjacency list to store graph connections

for u, v in edges:Build undirected graph by adding edges both ways

visited = set()Track nodes already visited to avoid revisiting

def dfs(node):Define DFS function to explore connected nodes

visited.add(node)Mark current node as visited to prevent cycles

for neighbor in graph[node]:Traverse all neighbors of current node

if neighbor not in visited:Recurse only on unvisited neighbors

count = 0Initialize count of connected components

for i in range(n):Check each node to start DFS if unvisited

if i not in visited:Start DFS only from unvisited nodes

count += 1Increment count for each new connected component found

return countReturn total number of connected components

import java.util.*;

public class NumberOfConnectedComponents {
    public static int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, graph, visited);
                count++;
            }
        }
        return count;
    }

    private static void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, graph, visited);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{1,2},{3,4}};
        System.out.println(countComponents(n, edges)); // Output: 2
    }
}

Line Notes

List<List<Integer>> graph = new ArrayList<>()Create adjacency list to represent graph

for (int i = 0; i < n; i++) graph.add(new ArrayList<>())Initialize empty adjacency lists for each node

for (int[] edge : edges)Build undirected graph by adding edges both ways

boolean[] visited = new boolean[n]Track visited nodes to avoid revisiting

if (!visited[i])Start DFS only from unvisited nodes

count++Increment count for each connected component found

visited[node] = trueMark current node as visited

for (int neighbor : graph.get(node))Traverse neighbors of current node

if (!visited[neighbor])Recurse only on unvisited neighbors

public static void main(String[] args)Driver code to test the function

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int countComponents(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);
    for (auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    vector<bool> visited(n, false);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, graph, visited);
            count++;
        }
    }
    return count;
}

int main() {
    int n = 5;
    vector<vector<int>> edges = {{0,1},{1,2},{3,4}};
    cout << countComponents(n, edges) << endl; // Output: 2
    return 0;
}

Line Notes

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited)DFS function to explore connected nodes

visited[node] = trueMark node as visited to avoid revisiting

for (int neighbor : graph[node])Traverse all neighbors of current node

if (!visited[neighbor])Recurse only on unvisited neighbors

vector<vector<int>> graph(n)Initialize adjacency list for n nodes

for (auto& edge : edges)Build undirected graph by adding edges both ways

vector<bool> visited(n, false)Track visited nodes

for (int i = 0; i < n; i++)Check each node to start DFS if unvisited

if (!visited[i])Start DFS only from unvisited nodes

count++Increment count for each connected component found

function countComponents(n, edges) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    const visited = new Set();
    function dfs(node) {
        visited.add(node);
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                dfs(neighbor);
            }
        }
    }
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            dfs(i);
            count++;
        }
    }
    return count;
}

// Driver code
const n = 5;
const edges = [[0,1],[1,2],[3,4]];
console.log(countComponents(n, edges)); // Output: 2

Line Notes

const graph = Array.from({length: n}, () => [])Initialize adjacency list for graph

for (const [u, v] of edges)Build undirected graph by adding edges both ways

const visited = new Set()Track visited nodes to avoid revisiting

function dfs(node)DFS function to explore connected nodes

visited.add(node)Mark node as visited

for (const neighbor of graph[node])Traverse neighbors of current node

if (!visited.has(neighbor))Recurse only on unvisited neighbors

let count = 0Initialize count of connected components

for (let i = 0; i < n; i++)Iterate over all nodes to start DFS if unvisited

count++Increment count for each connected component found

⏱

Complexity

TimeO(n + e)

SpaceO(n + e)

Building adjacency list takes O(e). DFS visits each node and edge once, so total O(n + e).

💡 For n=1000 and e=2000, this means roughly 3000 operations, which is efficient for interview constraints.

Interview Verdict: Accepted

This approach is efficient and accepted for large inputs, making it a solid baseline solution.

🧠

Union-Find (Disjoint Set Union)

💡 Union-Find is a powerful data structure to efficiently merge sets and find connected components without explicit graph traversal.

Intuition

Initialize each node as its own set. For each edge, union the sets of the two nodes. The number of unique parents after all unions is the number of connected components.

Algorithm

1. Initialize parent array where each node is its own parent.
2. Define find function with path compression to find root parent.
3. Define union function to merge two sets if they have different parents.
4. Iterate over edges and union their nodes.
5. Count how many nodes are their own parent to get number of components.

💡 The key is understanding how union merges sets and find identifies the root parent efficiently.

</>

Code

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
        self.count = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            self.count -= 1


def countComponents(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.count

# Driver code
if __name__ == '__main__':
    n = 5
    edges = [[0,1],[1,2],[3,4]]
    print(countComponents(n, edges))  # Output: 2

Line Notes

self.parent = list(range(n))Initialize each node as its own parent

self.rank = [0]*nRank array to keep tree shallow during union

def find(self, x)Find root parent with path compression

if self.parent[x] != xIf not root, recursively find root and compress path

def union(self, x, y)Union two sets if roots differ

if rootX != rootYOnly union if nodes belong to different sets

self.count -= 1Decrement count of components after successful union

for u, v in edgesUnion all connected nodes

return uf.countReturn number of connected components

public class NumberOfConnectedComponents {
    static class UnionFind {
        int[] parent, rank;
        int count;
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            count = n;
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        public int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
                else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
                else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
                count--;
            }
        }
    }

    public static int countComponents(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        return uf.count;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{1,2},{3,4}};
        System.out.println(countComponents(n, edges)); // Output: 2
    }
}

Line Notes

parent = new int[n]Initialize parent array with each node as its own parent

rank = new int[n]Rank array to optimize union operations

if (parent[x] != x)Path compression in find to flatten tree

if (rootX != rootY)Union only if roots differ

count--Decrease component count after union

for (int[] edge : edges)Union all connected nodes

return uf.countReturn number of connected components

public static void main(String[] args)Driver code to test the solution

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> parent, rank;
    int count;
    UnionFind(int n) : parent(n), rank(n, 0), count(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }
    }
};

int countComponents(int n, vector<vector<int>>& edges) {
    UnionFind uf(n);
    for (auto& edge : edges) {
        uf.unionSet(edge[0], edge[1]);
    }
    return uf.count;
}

int main() {
    int n = 5;
    vector<vector<int>> edges = {{0,1},{1,2},{3,4}};
    cout << countComponents(n, edges) << endl; // Output: 2
    return 0;
}

Line Notes

vector<int> parent, rankParent and rank arrays for union-find structure

UnionFind(int n) : parent(n), rank(n, 0), count(n)Initialize parent and rank arrays and count

for (int i = 0; i < n; i++) parent[i] = iEach node is its own parent initially

int find(int x)Find root parent with path compression

void unionSet(int x, int y)Union two sets if roots differ

if (rootX != rootY)Only union if nodes belong to different sets

count--Decrement count of connected components after union

for (auto& edge : edges)Union all connected nodes

return uf.countReturn number of connected components

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = Array(n).fill(0);
        this.count = n;
    }
    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY;
            } else if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX;
            } else {
                this.parent[rootY] = rootX;
                this.rank[rootX]++;
            }
            this.count--;
        }
    }
}

function countComponents(n, edges) {
    const uf = new UnionFind(n);
    for (const [u, v] of edges) {
        uf.union(u, v);
    }
    return uf.count;
}

// Driver code
const n = 5;
const edges = [[0,1],[1,2],[3,4]];
console.log(countComponents(n, edges)); // Output: 2

Line Notes

this.parent = Array.from({length: n}, (_, i) => i)Initialize each node as its own parent

this.rank = Array(n).fill(0)Rank array to keep trees balanced

if (this.parent[x] !== x)Path compression in find to flatten tree

if (rootX !== rootY)Union only if roots differ

this.count--Decrease count of connected components after union

for (const [u, v] of edges)Union all connected nodes

return uf.countReturn number of connected components

console.log(countComponents(n, edges))Driver code to test the function

⏱

Complexity

TimeO(α(n) * (n + e))

SpaceO(n)

Union-Find operations are almost O(1) amortized (α is inverse Ackermann function). We perform union/find for each edge and node.

💡 For n=1000 and e=2000, this is roughly 3000 near-constant time operations, very efficient.

Interview Verdict: Accepted

Union-Find is optimal for this problem and often preferred in interviews for its efficiency and elegance.

🧠

BFS Traversal

💡 BFS is an alternative to DFS for graph traversal. It uses a queue to explore neighbors level by level, which some find easier to implement iteratively.

Intuition

Start from each unvisited node, use a queue to explore all reachable nodes, marking them visited. Each BFS corresponds to one connected component.

Algorithm

1. Build adjacency list from edges.
2. Initialize visited set.
3. For each node, if unvisited, start BFS using a queue.
4. Mark all reachable nodes visited during BFS and increment component count.

💡 BFS uses a queue to explore neighbors in layers, which can be easier to visualize than recursion.

</>

Code

from collections import defaultdict, deque

def countComponents(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()
    count = 0

    for i in range(n):
        if i not in visited:
            queue = deque([i])
            visited.add(i)
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            count += 1
    return count

# Driver code
if __name__ == '__main__':
    n = 5
    edges = [[0,1],[1,2],[3,4]]
    print(countComponents(n, edges))  # Output: 2

Line Notes

from collections import defaultdict, dequeUse deque for efficient queue operations

graph = defaultdict(list)Build adjacency list for graph

visited = set()Track visited nodes

for i in range(n)Iterate over all nodes

if i not in visitedStart BFS from unvisited nodes

queue = deque([i])Initialize queue with starting node

visited.add(i)Mark starting node visited

while queueProcess nodes in BFS order

node = queue.popleft()Pop node from front of queue

for neighbor in graph[node]Traverse neighbors

if neighbor not in visitedAdd unvisited neighbors to queue and mark visited

count += 1Increment count for each connected component

import java.util.*;

public class NumberOfConnectedComponents {
    public static int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);
                visited[i] = true;
                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    for (int neighbor : graph.get(node)) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            queue.offer(neighbor);
                        }
                    }
                }
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{1,2},{3,4}};
        System.out.println(countComponents(n, edges)); // Output: 2
    }
}

Line Notes

List<List<Integer>> graph = new ArrayList<>()Create adjacency list

for (int i = 0; i < n; i++) graph.add(new ArrayList<>())Initialize adjacency lists

boolean[] visited = new boolean[n]Track visited nodes

if (!visited[i])Start BFS from unvisited nodes

Queue<Integer> queue = new LinkedList<>()Initialize queue for BFS

queue.offer(i)Add starting node to queue

visited[i] = trueMark starting node visited

while (!queue.isEmpty())Process nodes in BFS order

int node = queue.poll()Remove node from queue front

for (int neighbor : graph.get(node))Traverse neighbors

if (!visited[neighbor])Add unvisited neighbors to queue and mark visited

count++Increment count for each connected component

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int countComponents(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);
    for (auto& edge : edges) {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    vector<bool> visited(n, false);
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            queue<int> q;
            q.push(i);
            visited[i] = true;
            while (!q.empty()) {
                int node = q.front(); q.pop();
                for (int neighbor : graph[node]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
            count++;
        }
    }
    return count;
}

int main() {
    int n = 5;
    vector<vector<int>> edges = {{0,1},{1,2},{3,4}};
    cout << countComponents(n, edges) << endl; // Output: 2
    return 0;
}

Line Notes

vector<vector<int>> graph(n)Initialize adjacency list

for (auto& edge : edges)Build undirected graph

vector<bool> visited(n, false)Track visited nodes

if (!visited[i])Start BFS from unvisited nodes

queue<int> qInitialize queue for BFS

q.push(i)Add starting node to queue

visited[i] = trueMark starting node visited

while (!q.empty())Process nodes in BFS order

int node = q.front(); q.pop()Pop node from queue front

for (int neighbor : graph[node])Traverse neighbors

if (!visited[neighbor])Add unvisited neighbors to queue and mark visited

count++Increment count for each connected component

function countComponents(n, edges) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    const visited = new Set();
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            const queue = [i];
            visited.add(i);
            while (queue.length > 0) {
                const node = queue.shift();
                for (const neighbor of graph[node]) {
                    if (!visited.has(neighbor)) {
                        visited.add(neighbor);
                        queue.push(neighbor);
                    }
                }
            }
            count++;
        }
    }
    return count;
}

// Driver code
const n = 5;
const edges = [[0,1],[1,2],[3,4]];
console.log(countComponents(n, edges)); // Output: 2

Line Notes

const graph = Array.from({length: n}, () => [])Initialize adjacency list

for (const [u, v] of edges)Build undirected graph

const visited = new Set()Track visited nodes

if (!visited.has(i))Start BFS from unvisited nodes

const queue = [i]Initialize queue with starting node

visited.add(i)Mark starting node visited

while (queue.length > 0)Process nodes in BFS order

const node = queue.shift()Remove node from front of queue

for (const neighbor of graph[node])Traverse neighbors

if (!visited.has(neighbor))Add unvisited neighbors to queue and mark visited

count++Increment count for each connected component

⏱

Complexity

TimeO(n + e)

SpaceO(n + e)

Building adjacency list and BFS traversal each take O(n + e) time and space.

💡 For n=1000 and e=2000, BFS will perform about 3000 operations, efficient for interviews.

Interview Verdict: Accepted

BFS is a valid alternative to DFS and accepted in interviews, especially when iterative solutions are preferred.

📊

All Approaches - One-Glance Tradeoffs

💡 Union-Find is the best approach to code in most interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS)	O(n + e)	O(n + e)	Yes (deep recursion possible)	Yes	Good to explain and code if comfortable with recursion
2. Union-Find	O(α(n) * (n + e))	O(n)	No	No (but can be extended)	Optimal and preferred approach
3. BFS	O(n + e)	O(n + e)	No	Yes	Good iterative alternative to DFS

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, and finally optimize.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force DFS approach to find connected components.Step 3: Discuss Union-Find as an optimal solution.Step 4: Mention BFS as an alternative traversal method.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of graph traversal, ability to implement DFS/BFS or Union-Find, and handle edge cases efficiently.

Common Follow-ups

• How to detect cycles in the graph? → Use DFS with parent tracking or Union-Find with cycle detection.
• How to handle directed graphs? → Modify traversal or Union-Find accordingly.

💡 These follow-ups test your deeper understanding of graph properties and variations.

🔍

Pattern Recognition

When to Use

1) Problem involves undirected graph; 2) Need to find isolated groups or clusters; 3) Asked for count of connected components; 4) Input given as edges or adjacency list.

Signature Phrases

number of connected componentscount isolated groupsundirected graph connectivity

NOT This Pattern When

Problems about shortest paths, cycles detection without counting components, or directed graph strongly connected components

Similar Problems

Count Islands - similar DFS/BFS approach on gridGraph Valid Tree - uses connected components to verify treeNumber of Provinces - connected components in adjacency matrix

Practice

1. You need to find the cheapest route from a source city to a destination city with at most K stops in between. The graph edges represent flights with costs, and you want the minimum total cost under the stop constraint. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic programming using a 2D table indexed by stops and cities without priority queue.

B. A simple DFS with backtracking exploring all paths up to K stops.

C. A greedy algorithm that always picks the cheapest next flight regardless of stops.

D. Dijkstra's algorithm modified to track the number of stops along with cost.

Solution

1. Step 1: Understand the problem constraints

   The problem requires the cheapest path with at most K stops, so we must track both cost and stops.

2. Step 2: Identify suitable algorithm

   Dijkstra's algorithm can be adapted to track stops as a state parameter, ensuring paths exceeding K stops are not considered, guaranteeing optimality efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Modified Dijkstra tracks stops and cost simultaneously [OK]

Hint: Track stops in Dijkstra to enforce constraints [OK]

Common Mistakes:

• Assuming greedy cheapest next flight always works
• Using DFS without pruning leads to TLE
• Ignoring stops count in shortest path

2. Consider the following Python code for checking if a graph is a valid tree. What is the return value when calling valid_tree(4, [[0,1],[1,2],[2,3]])?

easy

A. true

B. false

C. Raises an exception

D. Returns null

Solution

1. Step 1: Check edge count

   Edges count is 3, nodes count is 4, so edges == n-1 condition passes.

2. Step 2: BFS traversal and cycle detection

   Starting from node 0, BFS visits nodes 0,1,2,3 without revisiting any node or detecting cycles. All nodes are visited.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph is connected and acyclic, so valid tree [OK]

Hint: Edges must be n-1 and BFS visits all nodes [OK]

Common Mistakes:

• Confusing cycle detection with revisiting parent
• Forgetting to check all nodes visited

3. Consider the following Python code implementing bidirectional BFS for the Word Ladder problem. Given beginWord = "hit", endWord = "cog", and wordList = ["hot", "dot", "dog", "lot", "log", "cog"], what is the returned value?

easy

A. 4

B. 5

C. 6

D. 0

Solution

1. Step 1: Trace initial sets and level

   begin_set = {"hit"}, end_set = {"cog"}, level = 1

2. Step 2: Expand begin_set neighbors and check for intersection

   Level 2: neighbors of "hit" include "hot"; no intersection yet. Level increments to 2.

3. Step 3: Expand smaller frontier each iteration until intersection

   Level 3: from "hot" neighbors "dot", "lot"; still no intersection. Level 4: from "dot", "lot" neighbors "dog", "log"; next level neighbors include "cog" which is in end_set, so return level + 1 = 4.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Shortest transformation length is 4 steps [OK]

Hint: Bidirectional BFS returns shortest path length 4 [OK]

Common Mistakes:

• Off-by-one in level counting
• Not updating visited correctly
• Returning 0 if endWord missing

4. Examine the following buggy code snippet for the optimal BFS approach. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line that sets dist[nr][nc] = dist[r][c] + 1 without checking if dist[nr][nc] == -1

B. Line that initializes dist[r][c] = 0 for land cells

C. Line that appends initial land cells to the queue

D. Line that returns -1 if all cells are land or water

Solution

1. Step 1: Identify that updating dist[nr][nc] without checking if it was visited causes overwriting distances.

   This leads to revisiting cells multiple times, causing infinite loops or incorrect distances.

2. Step 2: The missing condition dist[nr][nc] == -1 before updating and enqueueing is the bug.

   Without it, BFS does not behave correctly as a shortest path search.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited check prevents infinite loops and ensures correct distances [OK]

Hint: Always check if neighbor is unvisited before updating distance [OK]

Common Mistakes:

• Forgetting visited check causes infinite loops
• Misplacing initialization lines
• Incorrect early return conditions

5. Suppose the problem is modified so that you can only move in 4 directions (up, down, left, right) instead of 8. Which of the following statements about the shortest path algorithm is true?

hard

A. Greedy Best-First Search guarantees shortest path with 4-direction moves

B. Bidirectional BFS still finds the shortest path, but the path length may be longer due to restricted moves

C. DFS with backtracking becomes optimal since fewer directions reduce complexity

D. Dynamic Programming is required to handle the reduced movement directions

Solution

1. Step 1: Understand movement restriction impact

   Reducing to 4 directions limits possible paths, potentially increasing shortest path length.

2. Step 2: Evaluate algorithm suitability

   Bidirectional BFS still finds shortest path efficiently; DFS and greedy do not guarantee shortest path.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bidirectional BFS adapts to movement constraints, still optimal [OK]

Hint: Bidirectional BFS adapts to movement constraints [OK]

Common Mistakes:

• Assuming DFS or greedy become optimal
• Thinking DP is needed for movement changes