Tarjan Algorithms for SCC
I am stumbled at this part of SCC. I know that 5,6,7 is a strongly connected component. Performing the tarjan Algorithm for SCC starting at no de 5, I get unsatisfied values of low-link at 7.
Graph and DFS tree
let (x,y) ->(id,low-link)
Performing DFS(node 5),(5,5) I reached at node 6(6,6). From node 6 I have two out-adjacent edges one in-adjacent to node 5 and other one in-adjacent to node 7. Suppose choose the other one in-adjacent to node 7, (7,7). From node 7 there is only one out-adjacent edge going to node 6, which is already visited. Therefore I did the low-link update of (7,7) to (7,6). Then I backtrack to node 6 and explore the that out-adjacent edge going to node 5. So updated (6,6) to (6,5).Then again backtracking to node 5.
According Tarjan I should get (5,5),(6,5),(7,5) but I got (5,5),(6,5),(7,6)
Where did I go wrong?
It is not true that the low value for all nodes in a strongly connected component must be the same. It is only necessary that the first node visited in the DFS traversal of a strongly connected component have id[node] == low[node]. Any other node in the strongly connected component should have low[node] < id[node] as it can reach an earlier node through a back edge.
To actually process the strongly connected components, we can push each node onto a stack when it is first encountered in the DFS traversal. Once we identify the first node of a strongly connected component, we can remove all the nodes from the stack up until that node, which forms a strongly connected component.
- Mathematical explanation of Leetcode question: Container With Most Water
- How to check a point is inside an ellipsoid with orientation?
- algorithm to trace border in 2D array
- Red Black Tree Black Height Increase after Insertion
- Coin Change II : To take a value or not to
- Logic to implement to get maximum points
- Generate all strings under length N in C
- Algorithm to extract overlapping range
- Merging two sorted linked lists
- Median of two sorted-arrays algorithm for O(log(m+n))
- Calculating new longitude, latitude from old + n meters
- Calculation of Average Queue Length in a Simple Queueing Model
- what is the most efficient way to gather all points at a certain height?
- Does a recursive segment tree require more space than an iterative one?
- Tarjan Algorithms for SCC
- Is there a balanced BST with each node maintain the subtree size?
- Sort on a string that may contain a number
- Optimally counting number of nodes in a complete binary tree
- Fraction to Recurring Decimal
- Quicksort with Python
- What is the optimal algorithm for the game 2048?
- Asteroid Mining - Dynamic Programming problem
- Optimize performance for dense ranking algo
- Looking for a sort algorithm with as few as possible compare operations
- How to remove a line by its number from file without rewriting file python
- The output gives the same result
- Radix sort slower than expected compared to standard sort
- How to find minimum pairing cost? (Any Language)
- Algorithm to minimize the number of printing plates when printing sheets of stickers
- Travel from city 1 to city n, visiting at least 3 odd cities