How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Count Connected Components in an Undirected Graph

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given `n` nodes labeled from `0` to `n - 1` and a list of undirected edges. Each edge is represented as a pair `[u, v]`, meaning there is an undirected connection between node `u` and node `v`. Write a function that returns the number of connected components in the graph. A connected component is a maximal group of nodes where every node in the group can reach every other node in the same group through one or more edges. Example: ```text Input: n = 5 edges = [[0, 1], [1, 2], [3, 4]] Output: 2 Explanation: Nodes 0, 1, and 2 form one connected component. Nodes 3 and 4 form another connected component. ``` Follow-up: While processing the edges, how would you detect whether adding an edge connects two nodes that are already in the same component, indicating a cycle in an undirected graph?

Quick Answer: This question evaluates understanding of graph connectivity and cycle detection, measuring competency in reasoning about connected components and the use of appropriate graph data structures.

Part 1: Count Connected Components in an Undirected Graph

You are given an integer `n` and a list `edges`, where each element `[u, v]` represents an undirected edge between nodes `u` and `v`. Nodes are labeled from `0` to `n - 1`. Return the number of connected components in the graph. A connected component is a maximal set of nodes such that every node in the set can reach every other node in the set through one or more edges. Nodes with no edges count as their own components.

Constraints

0 <= n <= 100000
0 <= len(edges) <= 200000
Each edge is a pair `[u, v]` with `0 <= u, v < n` and `u != v`
The graph is undirected
Assume there are no duplicate edges

Examples

Input: (5, [[0, 1], [1, 2], [3, 4]])

Expected Output: 2

Explanation: Nodes 0, 1, and 2 form one component; nodes 3 and 4 form the other.

Input: (4, [])

Expected Output: 4

Explanation: There are no edges, so each node is its own connected component.

Input: (0, [])

Expected Output: 0

Explanation: An empty graph has zero connected components.

Input: (6, [[0, 1], [2, 3], [3, 4], [4, 2]])

Expected Output: 3

Explanation: Nodes 0 and 1 form one component, nodes 2, 3, and 4 form another, and node 5 is isolated.

Hints

Think of each node as starting in its own group. Every time you connect two different groups, the total number of components decreases by 1.
A Union-Find (Disjoint Set Union) structure can track component merges efficiently.

Part 2: Detect Whether an Added Edge Forms a Cycle in an Undirected Graph

You are given an integer `n` and a list `edges` describing undirected edges added to a graph one by one in the given order. Before adding an edge `[u, v]`, if `u` and `v` are already connected by an existing path, then adding `[u, v]` would create a cycle. Return `True` if any edge in the sequence creates a cycle; otherwise return `False`.

Constraints

0 <= n <= 100000
0 <= len(edges) <= 200000
Each edge is a pair `[u, v]` with `0 <= u, v < n` and `u != v`
The graph is undirected
Assume there are no duplicate edges

Examples

Input: (5, [[0, 1], [1, 2], [2, 0], [3, 4]])

Expected Output: True

Explanation: When edge [2, 0] is added, nodes 2 and 0 are already connected through 2-1-0, so a cycle is formed.

Input: (5, [[0, 1], [1, 2], [3, 4]])

Expected Output: False

Explanation: No edge connects two nodes that were already connected, so no cycle appears.

Input: (0, [])

Expected Output: False

Explanation: An empty graph has no edges, so no cycle can be formed.

Input: (4, [[0, 1], [1, 2], [2, 3], [0, 3]])

Expected Output: True

Explanation: Before adding [0, 3], nodes 0 and 3 are already connected through 0-1-2-3.

Hints

In an undirected graph, an edge creates a cycle exactly when its two endpoints are already in the same connected component.
Union-Find lets you check whether two nodes already share the same representative before merging them.

Quick Overview

This question evaluates understanding of graph connectivity and cycle detection, measuring competency in reasoning about connected components and the use of appropriate graph data structures.