43. Graphs-7 : Extra Algos

1. Kosaraju's Algorithm-

only for Directed graphs

QUES- find no. of  strongly connected components (SCCs) & print them

a strongly connected component is a component in which for every pair of nodes u,v we can go from u to v as well as from v to u

OBSERVATION-

1. in original graph, we can traverse bidirectionally within a SCC & unidirectionally b/w SCCs

2. when we reverse direction b/w 2 SCCs , then we can traverse only within a SCC not b/w the 2

3. since we don't know where are SCCs so we reverse all the edges instead


----------------------------------------------------------------
ALGO-
1. sort all edges according to finishing time
2. reverse the graph
3. do dfs
-------------------------------------------------------------
1. do dfs from starting node, when u reach an end insert it into a stack, and backtrack & insert similarly for other branches as well

2. reverse the edges- simple

3. take st.top() and start dfs and mark nodes vis and store them one by one into a vector

next pop those elements from stack which are vis & start dfs from first non visited you get & REPEAT

---------------------------------------------------

no. of SCCs = no. of dfs nodes in stack for which we did a dfs call

SCCs = stored in 2d vector

-------------------------------------------------

----------------------------------------------------------------------------------------------------------------------------

2. Tarjan's Algorithm-⭐

QUES- Bridges in graph or, finding non cyclic edges in a graph

we will use time array, lowestTime array & visited array

update the low of a node using the visited adjacent nodes ka low, except parent node
------------------------
to check if when an edge b/w 2 nodes is removed that if a new component is built or not-
see if,
time of parent node  > low of a node ==> no bridge
time of parent node < low of a node  ==> bridge found
----------------------
time of curr node = time of last visited node +1 
low of parent node = min low of (parent node, child/ adj node)
----------------------
do dfs till u reach a node from which u can't move further-->for a node---->set time & low to default values---->check if it has a visited adj node which ain't parent node--->update low of curr node--->backtrack to the parent node-->check if you can break the edge--->backtrack to parent node
----------------------------

----------------------------------------------------------------------------------------------------------------------------

3. Articulation points- ????

nodes on whose removal graph breaks into multiple components

a node is NOT an articulation point if its child node has a way to connect to its previous node

low of a node = min(low of curr node, time of adj node)

articulation pt : time of parent <= low of curr node 

---------------------------------------

1. use time & low arrays as u did in tarjan algo , but in low, along with parent this time also exclude visited nodes when updating low of a node
2. in the condition of checking articulation point add an extra condition of parent != -1

----------------------------------------

1. do dfs and mark time & low of all nodes with default values

2. when u reach a node whose all adj nodes are visited, then update this node's low

3. backtrack to its parent node & check parent node for condition of articulation point

4. again backtrack & repeat from step 2

-----------------------------------------------------------------------------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more