Strongly connected components in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Strongly Connected Components (SCC)

Which of the following best describes a strongly connected component in a directed graph?

A A subgraph that contains no cycles.

B A subgraph where there is at least one path between any two vertices, ignoring edge directions.

C A subgraph where every vertex is reachable from every other vertex within that subgraph.

D A subgraph where vertices have no incoming edges from outside the subgraph.

💡 Hint

Think about reachability in both directions between vertices.

A strongly connected component is a part of a directed graph where each vertex can be reached from any other vertex following the direction of edges.

📋 Factual

intermediate

Properties of Strongly Connected Components

Which statement about strongly connected components in a directed graph is true?

A A vertex can belong to multiple strongly connected components.

B Every vertex belongs to exactly one strongly connected component.

C Strongly connected components can overlap in vertices but not edges.

D Strongly connected components only exist in undirected graphs.

💡 Hint

Consider how SCCs partition the graph's vertices.

Strongly connected components form a partition of the graph's vertices, so each vertex belongs to exactly one SCC.

🚀 Application

advanced

Identifying SCCs Using Kosaraju's Algorithm

Given a directed graph, Kosaraju's algorithm finds strongly connected components by performing two depth-first searches (DFS). What is the main purpose of the first DFS?

A To find all cycles in the graph directly.

B To mark all vertices as visited to avoid revisiting.

C To reverse the edges of the graph.

D To compute the finishing times of vertices to order them for the second DFS.

💡 Hint

Think about how the order of processing vertices affects the second DFS.

The first DFS computes finishing times for vertices, which are used to order vertices in decreasing finishing time for the second DFS on the reversed graph.

🔍 Analysis

advanced

Time Complexity of SCC Algorithms

What is the time complexity of Tarjan's algorithm for finding strongly connected components in a graph with V vertices and E edges?

A O(V + E)

B O(V * E)

C O(V^2)

D O(E^2)

💡 Hint

Consider how many times each vertex and edge is processed.

Tarjan's algorithm runs in linear time relative to the number of vertices and edges, visiting each vertex and edge once.

❓ Reasoning

expert

Effect of Edge Direction on SCCs

Consider a directed graph where all edges are reversed. How do the strongly connected components of the reversed graph compare to those of the original graph?

A They are exactly the same sets of vertices forming the same strongly connected components.

B The reversed graph has no strongly connected components.

C They have the same vertices but different edges, so SCCs change.

D They are completely different and unrelated.

💡 Hint

Think about reachability in both directions and how reversing edges affects it.

Strong connectivity depends on mutual reachability. Reversing all edges preserves this property, so SCCs remain the same.