Strongly connected components in Data Structures Theory - Time & Space Complexity

Time Complexity: Strongly connected components

O(n + e)

Understanding Time Complexity

We want to understand how the time needed to find strongly connected components changes as the graph grows.

Specifically, how does the work increase when the number of nodes and edges increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findSCC(graph):
  stack = empty stack
  visited = empty set

  function dfs1(node):
    mark node visited
    for each neighbor in node's edges:
      if neighbor not visited:
        dfs1(neighbor)
    push node to stack

  for each node in graph:
    if node not visited:
      dfs1(node)

  transposeGraph = reverse all edges in graph
  visited.clear()

  function dfs2(node):
    mark node visited
    for each neighbor in node's edges in transposeGraph:
      if neighbor not visited:
        dfs2(neighbor)

  while stack not empty:
    node = pop from stack
    if node not visited:
      dfs2(node)
      output one strongly connected component

This code finds strongly connected components using two depth-first searches and a stack.

Identify Repeating Operations

• Primary operation: Depth-first search (DFS) traversals over nodes and edges.
• How many times: Each node and edge is visited a constant number of times (twice in total).

How Execution Grows With Input

As the number of nodes (n) and edges (e) grow, the DFS visits each node and edge once per traversal.

Input Size (n, e)	Approx. Operations
10 nodes, 15 edges	About 50 operations
100 nodes, 200 edges	About 600 operations
1000 nodes, 3000 edges	About 8000 operations

Pattern observation: The work grows roughly in direct proportion to the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time needed grows linearly with the total number of nodes and edges in the graph.

Common Mistake

[X] Wrong: "Because there are two DFS traversals, the time complexity is doubled and becomes quadratic."

[OK] Correct: Each DFS visits every node and edge only once, so the total work is still proportional to the sum of nodes and edges, not squared.

Interview Connect

Understanding this linear time complexity helps you explain how graph algorithms efficiently handle large networks, a valuable skill in many coding challenges.

Self-Check

"What if the graph was represented using an adjacency matrix instead of adjacency lists? How would the time complexity change?"