Graph Connectivity Checker — Problem Statement & Solution Guide

GraphsMediumMixed

TimeO(V + E)

SpaceO(V)

Problem Description

You are provided with an undirected graph represented as an adjacency list. The input is a dictionary where each key corresponds to a unique node identifier (an integer), and the value is a list of integers representing the nodes directly connected to it. Note that the graph may contain isolated nodes that appear as keys with empty neighbor lists, or nodes that are only referenced as neighbors but not explicitly defined as keys (though for this problem, assume all nodes are keys in the dictionary).

Your task is to determine whether the graph is connected. A graph is considered connected if there exists a path between every pair of distinct nodes. If the graph consists of a single node, it is trivially connected. If the graph is empty, it is considered connected.

Implement a function that returns the string 'Connected' if the graph is connected, and 'Not Connected' otherwise. You may use any standard graph traversal algorithm (BFS or DFS) to verify connectivity.

DSA Pattern Breakdown

"Graph Connectivity Checker"

medium

WHY DOES IT MATTER?

Connectivity checks are a foundational graph pattern used in network reliability, social‑network analysis, and clustering; recognizing when a problem reduces to a reachability query lets you apply a well‑optimized linear‑time traversal instead of costly exhaustive searches.

OPTIMIZATION CHALLENGE

The key insight is that you only need to propagate a single "visited" flag through edges once; by avoiding repeated edge examinations and by using adjacency lists, you achieve O(V+E) time and O(V) auxiliary space.

REAL-WORLD CONNECTION

Think of a power grid: each substation is a node and transmission lines are edges. Determining if the entire grid stays powered after a failure is exactly a connectivity check, and utilities use distributed BFS‑like algorithms to simulate outages in real time.

When coding in an interview, start with a simple recursive DFS for clarity, then quickly refactor to an iterative stack or queue to avoid recursion limits and to demonstrate control over space complexity.

COMPLEXITY AT A GLANCE

⏱ Time:O(V + E)

💾 Space:O(V)

Core Theory — Why This Approach?

The connectivity problem asks whether an undirected graph consists of a single connected component. The classic solution is to perform a graph traversal—Depth‑First Search (DFS) or Breadth‑First Search (BFS)—starting from any node and marking every visited vertex. After the traversal finishes, if every node (including isolated ones that appear only as keys) has been visited, the graph is fully connected; otherwise it is fragmented. A naïve approach might try to enumerate all possible paths between every pair of vertices, which leads to exponential blow‑up because the number of simple paths grows combinatorially with the number of edges. The optimal paradigm leverages the fact that connectivity is a transitive closure property: a single linear‑time traversal suffices to propagate reachability information across the entire component, yielding O(V+E) time. An alternative Union‑Find (Disjoint Set Union) structure can also achieve near‑linear performance by merging neighbor sets on the fly, but DFS/BFS remains the most intuitive and cache‑friendly for adjacency‑list representations.

Interview Questions on This Problem

Q1How would you modify the connectivity checker to also return the number of connected components in the graph?

Run DFS/BFS from an unvisited node, increment a component counter each time a new traversal starts, and continue until all nodes are visited; the counter then equals the number of connected components.

Q2Explain how Union‑Find can be used to solve the connectivity problem and compare its practical performance to DFS/BFS.

Initialize each node as its own set, then for every edge perform a union operation on its two endpoints. After processing all edges, check if all nodes share the same root. Union‑Find with path compression and union by rank runs in almost O(α(N)) per operation, but the constant factors and extra memory can make DFS/BFS faster for dense adjacency‑list graphs.

Q3In a massive distributed graph stored across multiple machines, what challenges arise when checking connectivity, and what high‑level strategy would you employ?

The main challenges are data locality and communication overhead. A common strategy is to run a parallel BFS using a message‑passing framework (e.g., Pregel or Spark GraphX) where each machine processes its local subgraph and exchanges frontier nodes, converging when no new nodes are discovered across the cluster.

Examples

Example 1

Input

{1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}

Output

Connected

Explanation: Start at node 1. Visit neighbors 2 and 3. From 2, visit 4. All nodes {1, 2, 3, 4} are visited. Since the number of visited nodes equals the total number of nodes, the graph is connected.

Example 2

Input

{1: [2], 2: [1], 3: [4], 4: [3]}

Output

Not Connected

Explanation: Start at node 1. Visit neighbor 2. Nodes {1, 2} are visited. Nodes 3 and 4 are not reachable from 1. Since not all nodes are visited, the graph is not connected.

Example 3

Input

{5: []}

Output

Connected

Explanation: The graph contains only one node (5). A single-node graph is trivially connected.

Example 4

Input

{1: [2, 3], 2: [1], 3: [1, 4], 4: [3], 5: []}

Output

Not Connected

Explanation: Start at node 1. Visit 2 and 3. From 3, visit 4. Nodes {1, 2, 3, 4} are visited. Node 5 is isolated and not visited. Therefore, the graph is not connected.

Constraints

1 <= number of nodes <= 10^5
Node identifiers are unique integers in the range [1, 10^5]
The adjacency list is symmetric: if node u is in the neighbor list of v, then v is in the neighbor list of u
The total number of edges is at most 10^5
All nodes are explicitly present as keys in the input dictionary

Optimal Approach & Strategy

Perform a single DFS or BFS from an arbitrary node, marking visited vertices. After the traversal, check if any node remains unvisited; this determines connectivity in O(V+E) time.

Brute Force Approach

A naive method would try to find a path between every pair of vertices by enumerating all possible routes, leading to exponential time. It also repeats work because the same edges are traversed many times.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(V + E)

function solution(graph) {
   const visited = new Set();
   function dfs(node) {
       visited.add(node);
       for (const neighbor of graph[node]) {
           if (!visited.has(neighbor)) {
               dfs(neighbor);
           }
       }
   }
   for (const node in graph) {
       if (!visited.has(node)) {
           dfs(node);
       }
   }
   return visited.size === Object.keys(graph).length ? 'Connected' : 'Not Connected';
}

class Solution {
   public string solution(unordered_map<string, vector<string>> graph) {
       set<string> visited;
       for (auto& node : graph) {
           if (visited.find(node.first) == visited.end()) {
               dfs(node.first, graph, visited);
           }
       }
       return visited.size() == graph.size() ? 'Connected' : 'Not Connected';
   }
   private void dfs(string node, unordered_map<string, vector<string>> graph, set<string>& visited) {
       visited.insert(node);
       for (auto& neighbor : graph[node]) {
           if (visited.find(neighbor) == visited.end()) {
               dfs(neighbor, graph, visited);
           }
       }
   }
};

class Solution {
   public String solution(Map<String, List<String>> graph) {
       Set<String> visited = new HashSet<>();
       for (String node : graph.keySet()) {
           if (!visited.contains(node)) {
               dfs(node, graph, visited);
           }
       }
       return visited.size() == graph.size() ? 'Connected' : 'Not Connected';
   }
   private void dfs(String node, Map<String, List<String>> graph, Set<String> visited) {
       visited.add(node);
       for (String neighbor : graph.get(node)) {
           if (!visited.contains(neighbor)) {
               dfs(neighbor, graph, visited);
           }
       }
   }
}

def solution(graph):
   visited = set()
   def dfs(node):
       visited.add(node)
       for neighbor in graph[node]:
           if neighbor not in visited:
               dfs(neighbor)
   for node in graph:
       if node not in visited:
           dfs(node)
   return 'Connected' if len(visited) == len(graph) else 'Not Connected'

function solution(graph) {
   const visited = new Set();
   function dfs(node) {
       visited.add(node);
       for (const neighbor of graph[node]) {
           if (!visited.has(neighbor)) {
               dfs(neighbor);
           }
       }
   }
   for (const node in graph) {
       if (!visited.has(node)) {
           dfs(node);
       }
   }
   return visited.size === Object.keys(graph).length ? 'Connected' : 'Not Connected';
}

Asked in Top Tech Interviews

graphsmediumiterative-approach

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Graph Connectivity Checker Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Graphs

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Graph Connectivity Checker — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor