MCQs

Disclaimer:

Educational Use Only:

The website links provided are to be used strictly for educational and knowledge-gaining purposes only.

No Misuse:

Do not misuse the links or the information contained therein for any commercial, illegal, or unethical activities.

Respect for Websites and Businesses:

Respect the intellectual property and business interests of the websites and their owners. Do not attempt to alter, copy, or redistribute content without proper authorization.

Acknowledge Value of Knowledge:

Recognize and value the knowledge and resources shared by these websites. Use the information responsibly and ethically.

No Endorsement:

The provision of these links does not imply endorsement of the linked sites, their content, or their products and services. Users are responsible for evaluating the suitability and accuracy of the information.

User Responsibility:

By accessing these links, you agree to use the information at your own risk and to comply with all applicable laws and website terms of use.

Overall MCQs for Reference

1. What defines a Strongly Connected Component (SCC) in a directed graph?
   a. A subgraph with no edges
   b. A subgraph where every vertex is reachable from every other vertex
   c. A subgraph with isolated nodes
   d. A graph with no cycles
   Answer: b
   Source:wikipedia+1​
2. Which algorithm is most commonly used to find Strongly Connected Components?
   a. Dijkstra’s Algorithm
   b. Floyd-Warshall Algorithm
   c. Tarjan’s Algorithm
   d. Kruskal’s Algorithm
   Answer: c
   Source:mauriciopoppe+1​
3. What is the time complexity of Tarjan’s algorithm for finding SCCs?
   a. O(n^2)
   b. O(m + n) where m is edges and n is vertices
   c. O(n log n)
   d. O(m^2)
   Answer: b
   Source:scaler+1​
4. In a strongly connected graph with n vertices, how many SCCs are there?
   a. Zero
   b. One
   c. n
   d. n-1
   Answer: b
   Source:tutorialspoint​
5. Which property must hold true for any vertex pair u, v in an SCC?
   a. There is a directed path from u to v but not necessarily from v to u
   b. No path exists between u and v
   c. There is a directed path from u to v and from v to u
   d. Vertices u and v are isolated
   Answer: c
   Source:tutorialspoint​
6. Tarjan’s algorithm uses which graph traversal method?
   a. Breadth-First Search (BFS)
   b. Depth-First Search (DFS)
   c. Dijkstra’s Algorithm
   d. Floyd-Warshall Algorithm
   Answer: b
   Source:mauriciopoppe+1​
7. What data structure is primarily used in Tarjan’s algorithm to track nodes?
   a. Queue
   b. Stack
   c. Linked List
   d. Hash Map
   Answer: b
   Source:mauriciopoppe​
8. What is the primary purpose of finding SCCs in graph-based machine learning applications?
   a. To optimize sorting algorithms
   b. To identify tightly linked groups or modules in data
   c. To compute shortest paths
   d. To analyze scalar values
   Answer: b
   Source:tutorialspoint+1​
9. Which of the following is NOT an application of SCCs in machine learning?
   a. Social network group detection
   b. Dependency analysis in software modules
   c. Generating random numbers
   d. Cycle detection in data flow
   Answer: c
   Source:tutorialspoint+1​
10. What kind of graph do SCC algorithms typically operate on?
    a. Undirected graphs
    b. Weighted graphs only
    c. Directed graphs
    d. Unconnected graphs
    Answer: c
    Source:mauriciopoppe​
11. In the context of SCCs, what is a “root” of a strongly connected component in Tarjan’s algorithm?
    a. The first discovered vertex in the component
    b. The vertex with the highest degree
    c. The vertex from which a DFS finishes last
    d. The vertex with minimum discovery time reachable from every node in the component
    Answer: d
    Source:mauriciopoppe​
12. What role do the “low-link values” play in Tarjan’s algorithm?
    a. They help detect cycles and back edges
    b. They find shortest path lengths
    c. They count the total number of edges
    d. They balance the graph’s weight
    Answer: a
    Source:mauriciopoppe​
13. How are SCCs related to Directed Acyclic Graphs (DAGs) in practice?
    a. SCCs form the nodes in the DAG after condensing cycles
    b. DAGs contain no SCCs by definition
    c. DAGs are always fully strongly connected
    d. SCCs cannot be created from DAGs
    Answer: a
    Source:upgrad+1​
14. Which is a known property of SCCs in social network analysis?
    a. They represent disconnected components
    b. They represent clusters of highly connected users
    c. They are rarely found
    d. They indicate outlier nodes
    Answer: b
    Source:neo4j+1​
15. Does an SCC contain cycles?
    a. Only if it is a trivial SCC of one node
    b. Yes, SCCs contain cycles or single nodes (self-loops)
    c. SCCs are always acyclic
    d. SCCs do not contain edges
    Answer: b
    Source:wikipedia+1​
16. What is the difference between connected components and strongly connected components?
    a. Connected components apply to undirected graphs, SCCs to directed graphs
    b. They are the same concept with different names
    c. Connected components apply only to weighted graphs
    d. SCCs apply only to acyclic graphs
    Answer: a
    Source:sciencedirect+1​
17. Which algorithm can be used alternatively to Tarjan’s algorithm to find SCCs?
    a. Kosaraju’s algorithm
    b. Prim’s algorithm
    c. Bellman-Ford algorithm
    d. Floyd-Warshall algorithm
    Answer: a
    Source:scaler+1​
18. In graph theory, what is a “sink” SCC?
    a. An SCC with no outgoing edges to other SCCs
    b. An SCC with no incoming edges
    c. The largest SCC
    d. A disconnected subgraph
    Answer: a
    Source:coursesidekick​
19. Why is the identification of SCCs important in software engineering?
    a. To optimize memory usage
    b. To detect circular dependencies between modules
    c. For UI design
    d. For compiling code efficiently
    Answer: b
    Source:tutorialspoint​
20. What is the space complexity of Tarjan’s algorithm?
    a. O(1)
    b. O(n)
    c. O(m^2)
    d. O(log n)
    Answer: b
    Source:mauriciopoppe​
21. What does SCC detection help with in the context of web crawling?
    a. To find disconnected websites
    b. To optimize crawling by identifying strongly connected subsets of the web
    c. To rank pages by popularity
    d. To speed up image recognition
    Answer: b
    Source:geeksforgeeks​
22. Which of the following graphs is guaranteed to have at least one SCC?
    a. Directed acyclic graph (DAG)
    b. Graph with a cycle
    c. Tree
    d. Empty graph
    Answer: b
    Source:testbook+1​
23. When running DFS in Tarjan’s algorithm, what condition tells you that a strongly connected component has been found?
    a. The discovery time equals the lowest reachable time
    b. DFS reaches a leaf node
    c. All nodes are visited
    d. One node remains unvisited
    Answer: a
    Source:mauriciopoppe​
24. How can SCCs assist in improving machine learning models?
    a. By identifying groups of features or samples that behave similarly
    b. By reducing dataset size arbitrarily
    c. By ignoring complex data structures
    d. By delaying training times
    Answer: a
    Source:scaler+1​
25. Which scenario would strongly connected components be most useful?
    a. Simplifying directed graphs by grouping cycles
    b. Sorting unordered arrays
    c. Fast multiplication of matrices
    d. Converting data types
    Answer: a
    Source:upgrad​
26. What kind of graph structure do SCCs partition?
    a. Directed graph into maximal strongly connected subgraphs
    b. Undirected graph into isolated nodes
    c. Weighted graphs into minimum spanning trees
    d. Cyclic graphs into trees
    Answer: a
    Source:programiz+1​
27. What is essential for a directed graph to be strongly connected?
    a. All vertices reachable from any vertex in at least one direction
    b. No cycles present
    c. Undirected edges only
    d. At least one isolated vertex
    Answer: a
    Source:tutorialspoint​
28. What distinguishes trivial SCCs?
    a. They consist of a single vertex with no cycle
    b. They contain multiple vertices
    c. They always include all graph vertices
    d. They have no edges
    Answer: a
    Source:wikipedia​
29. How does SCC detection impact graph compression?
    a. By collapsing strongly connected components into single nodes, reducing complexity
    b. By increasing the number of nodes
    c. By removing cycles only
    d. By adding redundant edges
    Answer: a
    Source:upgrad+1​
30. Which of the following best describes a cycle in the context of SCC?
    a. A path where the starting and ending vertices are the same
    b. A graph without any edges
    c. An undirected edge between two nodes
    d. A disconnected subgraph
    Answer: a
    Source:tutorialspoint​
31. Which property of the graph can be effectively analyzed by identifying SCCs?
    a. Connectivity and cycle detection
    b. Node degree distribution
    c. Edge weight sum
    d. Minimum spanning tree
    Answer: a
    Source:tutorialspoint​
32. How can SCCs be applied in recommendation systems?
    a. By grouping users or items with mutual interactions
    b. By ignoring user preferences
    c. By randomly selecting recommendations
    d. By sorting data in ascending order
    Answer: a
    Source:neo4j+1​
33. Which is a practical benefit of SCC analysis in complex networks?
    a. It reveals bottlenecks and redundancies in connectivity
    b. It removes all edges
    c. It isolates nodes individually
    d. It reduces the number of vertices to zero
    Answer: a
    Source:meegle​
34. What happens to SCCs if a vertex is removed from the graph?
    a. SCCs may split or reduce in size depending on connectivity
    b. Nothing changes
    c. All components merge
    d. The graph becomes empty
    Answer: a
    Source:testbook​
35. Which step is NOT part of Tarjan’s algorithm for SCC detection?
    a. Initialization of discovery times
    b. DFS traversal
    c. Back edge detection
    d. Random node deletion
    Answer: d
    Source:mauriciopoppe​
36. Which industry extensively uses strongly connected components for fraud detection?
    a. Financial institutions
    b. Agriculture
    c. Textile manufacturing
    d. Retail groceries
    Answer: a
    Source:meegle​
37. How do SCCs assist in parallel computing?
    a. By identifying independent subgraphs for concurrent processing
    b. By serializing the tasks only
    c. By increasing dependency between tasks
    d. By limiting memory usage
    Answer: a
    Source:tutorialspoint​
38. What is the function of “in_stack” array in Tarjan’s algorithm implementation?
    a. Indicates whether a vertex is currently on the stack during DFS
    b. Holds vertex degrees
    c. Stores final component IDs
    d. Counts graph edges
    Answer: a
    Source:mauriciopoppe​
39. How does Kosaraju’s algorithm find SCCs?
    a. By running DFS twice, once in original and once in reverse graph
    b. By sorting nodes by degree
    c. By trimming edges randomly
    d. By breadth-first search only
    Answer: a
    Source:scaler​
40. Which is a major challenge in finding SCCs in large graphs?
    a. Managing memory efficiently while traversing
    b. Lack of path data
    c. Absence of cycles
    d. Undirected edges
    Answer: a
    Source:meegle​
41. What role does SCC identification have in circuit design analysis?
    a. To detect feedback loops and subcircuits
    b. To remove circuits completely
    c. To reorder components randomly
    d. To eliminate all connections
    Answer: a
    Source:tutorialspoint​
42. For a graph G with n vertices and m edges, what does m represent?
    a. Number of edges
    b. Number of vertices
    c. Number of SCCs
    d. Number of disconnected components
    Answer: a
    Source:mauriciopoppe​
43. Can strongly connected components exist in undirected graphs?
    a. No, only connected components exist in undirected graphs
    b. Yes, SCC is defined for all graphs
    c. Only if the graph is complete
    d. Only if the graph has cycles
    Answer: a
    Source:mauriciopoppe​
44. Why are SCCs important in model checking and verification?
    a. To identify strongly connected behavior states for correctness proofs
    b. To simplify programming languages
    c. To encrypt data
    d. To speed up compilation
    Answer: a
    Source:stackoverflow​
45. What metric can be used to evaluate the size of SCCs in real graphs?
    a. Number of nodes in each SCC
    b. Total edge weight
    c. Sum of external edges
    d. Frequency of isolated nodes
    Answer: a
    Source:neo4j​
46. Which of these is NOT true about SCCs?
    a. Each node belongs to exactly one SCC
    b. SCCs can overlap with each other
    c. SCCs partition a graph’s nodes
    d. Each SCC is a maximal strongly connected subgraph
    Answer: b
    Source:wikipedia​
47. How do SCC algorithms assist in knowledge graph optimization?
    a. By consolidating strongly connected entities for efficient queries
    b. By randomly deleting nodes
    c. By ignoring relationships
    d. By sorting node names alphabetically
    Answer: a
    Source:neo4j+1​
48. What indicates that a directed graph is not strongly connected?
    a. Existence of at least one vertex unreachable from another
    b. Presence of cycles
    c. Graph has weighted edges
    d. Graph is undirected
    Answer: a
    Source:tutorialspoint​
49. Which data science task can leverage SCC decomposition?
    a. Community detection in networks
    b. Linear regression
    c. Data normalization
    d. Principal Component Analysis
    Answer: a
    Source:tutorialspoint​
50. Which of the following is a key characteristic of Tarjan’s algorithm?
    a. Uses DFS and a stack to find SCCs in a single pass
    b. Uses BFS only
    c. Requires multiple passes over the graph
    d. Ignores back edges
    Answer: a
    Source:scaler+1​

1. https://en.wikipedia.org/wiki/Strongly_connected_component
2. https://www.programiz.com/dsa/strongly-connected-components
3. https://www.mauriciopoppe.com/notes/computer-science/data-structures/graphs/components/
4. https://www.scaler.com/topics/data-structures/strongly-connected-components/
5. https://www.tutorialspoint.com/graph_theory/graph_theory_strongly_connected_graphs.htm
6. https://www.tutorialspoint.com/data_structures_algorithms/strongly_connected_components.htm
7. https://neo4j.com/docs/graph-data-science/current/algorithms/strongly-connected-components/
8. https://www.upgrad.com/tutorials/software-engineering/data-structure/strongly-connected-components/
9. https://www.sciencedirect.com/topics/computer-science/connected-component
10. https://www.coursesidekick.com/computer-science/1689085
11. https://www.geeksforgeeks.org/dsa/strongly-connected-components/
12. https://testbook.com/objective-questions/mcq-on-connected-and-strongly-connected-graph–5eea6a0a39140f30f369dc0c
13. https://www.meegle.com/en_us/topics/algorithm/strongly-connected-components-algorithms
14. https://stackoverflow.com/questions/11212676/what-are-strongly-connected-components-used-for
15. https://testbook.com/objective-questions/mcq-on-connected-and-strongly-connected-components–5eea6a0a39140f30f369dc0a
16. https://www.geeksforgeeks.org/quizzes/top-mcqs-on-graph-traversals-with-answers/
17. https://www.tutorialspoint.com/data_structures_algorithms/quiz_on_strongly_connected_components.htm
18. https://www.geeksforgeeks.org/quizzes/top-mcqs-on-graph-traversals-with-answers/?page=3
19. https://interviewkickstart.com/blogs/interview-questions/algorithm-design-analysis-mcqs
20. https://examradar.com/fundamentals-of-algorithms-and-problem-solving-mcqs/