We know that Kosaraju-Sharir's algorithm can be used to find the Strongly Connected Components (SCCs) of a graph. It is composed of three main tasks: 

  1. Get Decreasing Order of DFS Finishing Times
  2. Traverse the Reverse Graph
  3. Each Tree is a Strongly Connected Component
Given that, and the following graph:



Select the alternative that has the correctly DFS decreasing order of finishing times starting from node A, the correctly reverse graph and, finally, each SCC colored correctly.




      e) None of the above.                                                  




Original idea by: Matheus de Oliveira Saldanha



Comentários

Postar um comentário

Postagens mais visitadas deste blog

Imagem
Using the Breath-First-Search (BFS) algorithm, how many nodes have a distance of 1, 2 and 3 from node A, respectively? a) 2, 4, 3 b) 3, 3, 3 c) 3, 4, 2 d) 2, 3, 4 e) None of the above. Original idea by: Matheus de Oliveira Saldanha
Leia mais
Evaluate the following affirmations regarding planarity and planarity testing algorithms: I. A multi-graph is considered planar when it admits a plane drawing . II. To postulate Euler's formula ( $N-L+F=2$ ), one can start with a single node and observe        the  effect on $N$ , $L$ , and $F$ when adding a new node connected to an existing node, or when    adding a link between two existing nodes . III.  Kuratowski's Theorem states that a graph is planar if and only if it contains a subdivision (the process of replacing a link by a path) of $K_{3,3}$ or of $K_{5}$ , effectively making them mandatory subgraphs for planarity . IV. The pseudo-code for the DMP algorithm begins by starting with a single node and iteratively selects a fragment $B$ with the maximum number of faces $F(B)$ that contain all its vertices of attachment . V.  When using the DMP algorithm, a fragment of a graph $G$ with respect to a subgraph $H$ can be an...
Leia mais
Imagem
Jerry the mouse is trying to reach a piece of cheese located somewhere in a maze. The maze can be represented as a graph , where: Each node is labeled with a letter and a number (for example: A1, D2, F3). Edges represent paths between locations in the maze . Jerry starts at node D2 and explores the maze using Depth-First Search (DFS) . When DFS needs to choose which neighbor to visit next, Jerry must follow one consistent ordering rule . However, he is not sure which rule will lead him to the cheese the fastest. Jerry is considering the following four DFS neighbor ordering strategies: Order neighbors by the letter only, ascending (A → Z) Order neighbors by the letter only, descending (Z → A) Order neighbors by the number only, ascending (1 → 9) Order neighbors by the number only, descending (9 → 1) Assume that when sorting neighbors, the ignored part of the label is not considered . The cheese is located at node  J2 . Which of the following alterna...
Leia mais