2026-342

A secret organization suspects that some gang members form closed communication groups, that is, groups in which any member can send or receive messages from other members of the group, passing only through members of that group. To understand the communication traffic between these members, the organization created the following graph.

What are the closed communication groups of the gang members?

A) {Michael, Sophie, Daniel, Olivie, Lucas, Emma, ​​Ryan}, {Chloe, Ethan}

B) {Michael, Sophie, Daniel}, {Olivie, Lucas}, {Emma, ​​Ryan, Chloe}, {Ethan}

C) {Chloe}, {Ethan}, {Michael, Sophie, Daniel, Olivie, Lucas}, {Emma, ​​Ryan}

D) {Michael, Sophie, Daniel, Olivie}, {Lucas, Emma, ​​Ryan}, {Chloe}, {Ethan}

E) None of the above

Original idea by:  Angelica Santos

2026-335

Maria studies at UNICAMP and is taking a Graph Algorithms class. Driven by curiosity, she applied what she learned in class to a network generated from her classmates' profiles on the social media platform Z. The nodes of the network are Maria's classmates and an outgoing edge indicates following someone, while an incoming edge indicates being followed by someone. 

She wanted to identify specific clans and see if there were any isolated classmates. Her goal was to bring those people into a community to ensure no one feels alone in class. Could you help her identify the number of communities and isolated profiles in this network?

Maria defines a clan as any group of classmates forming a Strongly Connected Component (SCC) of two or more people (nodes). Any classmate who belongs to an SCC of only one person (node) is considered an isolated profile.

a) There are 3 communities and 4 isolated profiles.

b) There are 2 communities and 4 isolate profiles.

c) There are 1 community and 6 isolated profiles.

d) There are 1 community and 4 isolated profiles.

e) None of the above.

Original idea by: Melissa Araújo

2026-334

In a directed graph define two functions:

\( f(u, v) \): there exists a directed path from \(u\) to \(v\) .

\( scc(u) \) : Returns the SCC containing node \(u\).

For each of the following logical statements, determine whether it is True or False for any arbitrary directed graph:

1. \( scc(u) = scc(v) \Longrightarrow f(u,v) \)
2. \( (f(u,v) \) and \( f(v,u)) \Longleftrightarrow scc(u) = scc(v) \)
3. \( f(u,v) \Longrightarrow scc(u) = scc(v) \)
4. \( (f(u,v) \) and \( f(v,w)) \Longrightarrow f(u,w) \)

---

Alternatives

a) TTFT
b) TFFF
c) TFFT
d) TTTT
e) None of the above

Original idea by: Luis Alberto Vásquez Vargas

2026-333

A delivery driver is working in a neighborhood where the streets are one-way. He serves one restaurant (R1) and has received 6 delivery requests (C1 to C6) from different customers in that neighborhood. The graph below represents the routes, respecting the directions of the streets. 

The driver will try and satisfy as many requests as possible, but must return to the restaurant after serving customers to receive his payment, without violating the street directions. After picking up the orders at the restaurant, which of the following alternatives is correct? 

(A) All customers would receive their orders.

(B) Only customers C1 and C3 would receive their orders.

(C) Customers C5 and C6 would not receive their orders.

(D) Only customer C1 and C2 would receive their order.

(E) None of the alternatives.

Original idea by: Ingrid Barbosa

2025-310

Which of the following alternatives contains a graph with only one Strongly Connected Component (SCC)? 

a)

b)

c) 

d)

 

e) None of the above


Original idea by: Pedro Zaffalon da Silva

2025-309

The Kosaraju–Sharir algorithm is used to identify strongly connected components (SCCs) in directed graphs. It runs in O(V + E) time, since it performs two depth-first searches (DFS) and uses the transposed graph.

Consider the directed graph with vertices {0, 1, 2, 3, 4, 5, 6, 7} and edges:

(0 → 1), (1 → 2), (2 → 0), (2 → 3), (3 → 4), (4 → 5), (4 → 6), (5 → 6), (6 → 7), (7 → 4)

Regarding the application of the Kosaraju–Sharir algorithm to this graph, select the correct alternative:

a) The algorithm finds three strongly connected components: {0,1,2}, {3} and {4,5,6,7}.

b) The algorithm finds four strongly connected components: {0,1,2}, {3}, {4,5,6} and {7}.

c) The algorithm cannot be applied to directed graphs, only to undirected graphs.

d) The algorithm finds eight strongly connected components, each vertex being isolated.

e) None of the above.

Original idea by: Pedro Pereira

2023-216

Which of the following statements is true about the Kosaraju-Sharir algorithm?

A) It is used to find the shortest path between two nodes in a graph.

B) It is a greedy algorithm that always finds the optimal solution.

C) It is used to determining the strongly connected components in a directed graph.

D) It is used to computing the minimum spanning tree of a graph

E) None of the above.

Original idea by: Arthur Hendricks.

2025-261

Consider a directed graph \(G\) and the Kosaraju-Sharir algorithm for finding strongly connected components (SCCs). Analyze the following statements:

I. The SCC decomposition of a directed graph is unique, but the particular order in which SCCs are discovered by Kosaraju-Sharir’s algorithm may depend on the order of adjacency lists.

II. If a directed graph has no back edges in a DFS traversal, then each vertex forms a distinct SCC.

III. If \(G\) is strongly connected, then the second DFS in Kosaraju-Sharir’s algorithm produces a single tree covering all vertices, regardless of the order of exploration.

IV. The order of vertices given by decreasing finishing times of the first DFS guarantees that the second DFS on the transposed graph \(G^T\)$$discovers one SCC at a time.

Select the correct alternative:

A) Only I and II are correct.
B) Only I and IV are correct.
C) Only I, II and IV are correct.
D) Only I, III and IV are correct.
E) None of the above.

Original idea by: Mateus de Padua Vicente

2025-260

A technical leader responsible for the software testing team intends to allocate a functional requirement to a team member who currently has no assigned tasks. For this assignment, the objective is to select a functional requirement that does not have strong dependencies on other requirements. Therefore, the leader chose to use the Kosaraju-Sharir algorithm to identify the Strongly Connected Components composed of only a single vertex.  Requirement dependencies are represented in the directed graph shown in the image below.

Which functional requirement was assigned to the team member for testing?

    A. FR01

    B. FR03

    C. FR05

    D. FR07

    E. None of the above

Original idea by: Jonas Henrique Ribeiro Paula

2025-259

Consider the following directed graph:

I. The shortest path from A to J has length 5, and this is the longest among all shortest paths in the graph.

II. The number of cycles in the graph is exactly half the number of its strongly connected components.

III. If each strongly connected component is collapsed into a single node, there will be two possible topological orderings of the graph.

IV. If node D and all its incident edges are removed, and a new edge from B to E is added, the resulting graph will form a single strongly connected component.

Which of the statements are correct?

A) I, II, and III

B) Only III

C) III and IV 

D) Only IV

E) None of the above

Original idea by: Jhonatan Cléto

2024-245

The Kosaraju-Sharir algorithm is designed to find all Strongly Connected Components (SCCs) in a directed graph. Which of the following alternatives correctly describes the main phases of the algorithm?

 

A - Perform a DFS on the graph to compute the finishing times of each vertex. Then, reverse the graph and perform another DFS based on decreasing finishing times.

B - Perform a BFS (Breadth-First Search) on the graph, followed by sorting the nodes based on their distances from the start vertex. Then, reverse the graph and repeat the BFS.

C - Reverse the graph, perform a DFS, and then compute a topological sort of the graph to find SCCs.

D - Use Dijkstra's algorithm to find the shortest path to each vertex, then reverse the graph and repeat the process.

E - None of the above

Original idea by: Vanessa Oliveira Alves

2024-244

The goal of Kosaraju-Sharir's algorithm is to find all strongly connected components (SCCs) of a given input graph. Please take into consideration the directed graph provided below and select the appropriate alternative about the decomposition of the graph into SCCs using this algorithm.

A. Starting from A and using alphabetical order to apply the first DFS, node G has minimum (equal to 4) finishing time. 

B. Starting from A and using alphabetical order to apply the first DFS, node A has maximum (equal to 10) finishing time.

C. Each node of the graph is a strongly connected component.

D. {A, B, C, G, F}, {D}, and{E} are strongly connected components of the graph.

E. None of the above.

Original idea by: Karla Florentino

2023-217

Taking into consideration the directed graph below, in the context of Strongly Connected Components (SSCs), choose the most appropriate alternative:

a) This graph has an even number of SCCs and not all the components' numbers of nodes are prime numbers.

b) The largest SCC (with the greatest number of nodes) is precisely the first SCC found by Kosaraju-Sharir's algorithm.

c) More than half of the SCCs in the graph have 3 nodes.

d) This graph has 5 SCCs, the smallest of which is formed by 'k' alone.

e) None of the above. 

Original idea by: João Marcos

2023-215

Given the following directed graph, if we executed Kosaraju-Sharir’s algorithm to detect its strongly connected components (SCCs) starting at node A and assuming the adjacency lists are sorted in descending order (Z to A), what would the SCCs be and in which order they would be returned?

1. 2 SCCs returned: BDCA first and then FGH;
2. 2 SCCs returned: FGH first and then BDCA;
3. 4 SCCs returned: H first, then G, F, and BDCA;
4. 4 SCCs returned: BDCA first, then F, G, and H;
5. None of the above.

Original idea by: Fillipi Valadares

2023-214

Consider the following directed graph:

In order to apply the Kosaraju-Sharir algorithm, a DFS was performed and the following start and end times were computed:

What will be the first strongly connected component detected in this graph?

1. {7}.
2. {4, 5, 6}.
3. {2, 3, 4}.
4. {1, 2, 3}.
5. None of the above

Original idea by: Christian Konishi

2023-213

 Considering the following directed graph:

I. Since this is a strongly connected graph, it does not have a topological sort.

II. We can easily find a topological sort for this graph using the reverse order of finishing times from DFS.  

III. By applying Kosaraju-Sharir’s algorithm to this graph, we will obtain a set of strongly connected components in the order [{C}, {D, E, F}, {A}, {B}].

IV. Kosaraju-Sharir’s algorithm can find the topological sort of any directed graph even if it has cycles, in this case treating each strongly connected component as a single node. In this particular graph, the last node in the topological sort could be either A or B.

What statements from the options above are correct?

1. I and III
2. II and IV
3. III
4. III and IV
5. none of above

Original idea by: Anderson Nogueira Cotrim

2022-181

The Kosaraju-Sharir algorithm is an algorithm used to find strongly connected components in a graph.

Applying the algorithm on the graph given above, how many strongly connected components do we find, and what is the size of the biggest component, and the size of the smallest? (respectively)

1. 4, 7, 2
2. 4, 8, 1
3. 5, 6, 2
4. 6, 5, 1
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

2022-180

Consider the directed graph given below and select the correct alternative that best decompose the graph into strongly connected components.

A.{P, Q, R, S}, {T}, {U}, {V}

B.{P, Q, S, T, V}, {R}, {U}

C.{P, Q, R, S, T, U, V}

D.{P, Q, R, S, T, V}, {U}

E. None of the above

Original idea by: Muhammad Idrees

2022-179

Consider the following statements about strongly connected components (SCC):

1. The graph \(G'\), obtained by contracting the strongly connected components of \(G\), is necessarily acyclic.
   
2. The strongly connected components of a graph \(G\) and its transpose \(G^T\) are the same.
   
3. It is possible to use the DFS algorithm to find the strongly connected components of a graph. More specifically, two DFS executions must be performed, and the first one is used to find the order of seeds for the second execution.
   

The true statements are:

1. I, II and III
   
2. II and III
   
3. II
   
4. III
   
5. None of the above.

Original idea by: André Nóbrega

2022-103

Consider the following statements about strongly connected components (SCC):

1. All strongly connected components in a bipartite, directed network have an even number of nodes.
   
2. The Kosaraju-Sharir algorithm uses the BFS-algorithm two times in order to get the SCCs of a network.
3. A single node may be classified as a strongly connected component in a network.

The only statements above that are correct are:

1. I and III
2. II and III
3. I and II
4. Only III
5. None of the above

Original idea by: Athyrson M. Ribeiro