Problem

Given an undirected graph, write an algorithm to check if it is connected (i.e., there is a path between every pair of vertices).

Input Format:

  • The graph is represented as an adjacency list: a list of n lists, where adj[i] contains all nodes adjacent to node i.
  • For example, adj = [[1,2],[0,2],[0,1,3],[2]] represents a graph with 4 nodes (0 to 3), where node 0 is connected to nodes 1 and 2, node 1 to 0 and 2, etc.

Definitions

Undirected Graph Connectivity Definition

Examples

Example 1

graph LR
	A(0) --- B(1) & C(2)
	B --- C
	C --- D(3)
  
1
2
3

Input: n = 4, adj = [[1,2],[0,2],[0,1,3],[2]]
Output: true
Explanation: All nodes are reachable from any node, so the graph is connected.

Example 2

graph LR
	A(0) --- B(1)
	B --- C(2)
	D(3) --- E(4)
  
1
2
3

Input: n = 5, adj = [[1],[0,2],[1],[4],[3]]
Output: false
Explanation: There are two disconnected components: nodes 0-1-2 and nodes 3-4. Not all nodes are reachable from each other.

Solution

Method 1 – Depth-First Search

Intuition

If we can reach all nodes from any starting node using DFS, the graph is connected.

Approach

  1. Start DFS from any node (e.g., node 0).
  2. Mark all visited nodes.
  3. After DFS, check if all nodes are visited.
  4. If yes, the graph is connected; otherwise, it is not.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
	void dfs(int u, const vector<vector<int>>& adj, vector<bool>& vis) {
		vis[u] = true;
		for (int v : adj[u]) if (!vis[v]) dfs(v, adj, vis);
	}
	bool isConnected(int n, vector<vector<int>>& adj) {
		vector<bool> vis(n, false);
		dfs(0, adj, vis);
		for (bool v : vis) if (!v) return false;
		return true;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
	public boolean isConnected(int n, List<List<Integer>> adj) {
		boolean[] vis = new boolean[n];
		dfs(0, adj, vis);
		for (boolean v : vis) if (!v) return false;
		return true;
	}
	private void dfs(int u, List<List<Integer>> adj, boolean[] vis) {
		vis[u] = true;
		for (int v : adj.get(u)) if (!vis[v]) dfs(v, adj, vis);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
	def is_connected(self, n: int, adj: list[list[int]]) -> bool:
		vis = [False] * n
		def dfs(u):
			vis[u] = True
			for v in adj[u]:
				if not vis[v]:
					dfs(v)
		dfs(0)
		return all(vis)

Complexity

  • ⏰ Time complexity: O(V + E), where V is the number of vertices and E is the number of edges.
  • 🧺 Space complexity: O(V), for the visited array and recursion stack.