42. Graphs-6 : MST, DSU

TOPICS-

• MST
• Prim's algo (greedy)
• DSU
• Kruskal Algo (using dsu)

--------

• No. of provinces        (no. of components in graph)
• Connected networks  (no. of extra edges in a component)
• Merged accounts       (dsu + hash map)⭐
• no. of islands 2          (dsu + matrix) / (using size vector of dsu)
• stones removal          (dsu + treating each row & col as a node)

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

Minimum Spanning Tree-

1. Spanning tree: has (n) nodes and (n-1) edges & all nodes are reachable from each other & do not has cycles
2. A graph can have any no. of spanning trees.
3. Out of all spanning trees, the tree with min sum of all edge weights is called MST of a graph

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

Prim's Algo-

time: ElogE

1. For UG graph with weighted edges
2. used to find mst 

3. here, make a tree greedily by growing it, at each step, with node having cheapest cost 

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

initialize pq with {0,0,-1}: { wt, node, parent }

initialize vis array with all elements being 0

You need parent to be stored for each node in the priority queue if mst is asked,
elsewise if directly the min sum is asked , we do not need it
-----------------------------

1. pop out element from pq
2. if it is vis then skip and go to step 6,
3. if it is unvis, then:
   3.1) mark it as visited 
   3.2) add (parent, node) this edge, to mst list, if this is not the first node

   3.3) update the sum

   3.4) iterate over its unvis neighbors and push them into pq
4. Repeat

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

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

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

Disjoint Set-⭐

• it is a custom data structure used for dynamic graphs which keeps changing their configuration
• it gives 2 functionalities- finding parent
                                           union:- joining nodes (by rank or by size)
• we can also answer in constant time, at any step of graph changing , that whether 2 nodes are connected or not, OR
  we can tell in constant time whether 2 nodes belong to same component or not

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

Union By Rank-

time: O(4ɑ) ~  constant

we need-

parent array (size = N & initialized with arr[i] = i )

rank array    (size = N & initialized with 0s)

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

rank of a node => it can be thought as height of tree (in terms of edges) which is rooted at this node

parent of a node => what node is above the curr node

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

for each element in edge list-  (node: u ,node: v) means edge b/w u & v 

1. find ultimate parents: pu, pv

2. find rank of pu & pv

3. Always connect smaller rank to larger rank (in case of equality, connect anyone to anyone)      

4. now update the parent & rank of respective nodes out of the 2 (rank increases on union only in case of equal ranks of pu, pv)

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

below code works for both 0 based & 1 based indexing graphs-

-----------------------------------------------------------------------------------------------------------------------------
NOTE-

1. we tell if 2 nodes belong to same component by comparing their ultimate parents

----------------------------------------------
2. Although it takes logN time at first for finding parent, but due to path compression, for later stages, it is done in constant time. And also after path compression rank is not changed because it is rank and not height
e.g., here graph was (5->4->3->2->1) so, once we find ultimate parent of 5, then we backtrack & updates the ultimate parent of all nodes beneath 1

3. why connect smaller to larger ?
because whenever we connect a to b then distance covered by nodes in a to reach ultimate parent increase , so if we choose a to be of smaller rank or size then there will be lesser no. of nodes that will have to travel larger distance to find their parent

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

Union By Size-

instead of rank, keep a track of size of component

size(x) => no. of nodes(including x) in the tree rooted at x 

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

1. initialize size[ ] with all elements as 1

2. if size(pu)= size(pv), attach any one to any one

else, attach smaller sized node to larger sized node 

3. update size[] & parent[]
----------------------------

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

NOTE-

1. in union by rank- we update rank[]   ,  when rank(u) = rank(v)

2. in union by size⭐-we update size[] ,  in both cases

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

Kruskal Algo-

It is used to make a MST out of a given graph using DSU and a greedy approach
-------------------------------------

1. sort all edges as per weight

2. now do union b/w 2 nodes if they do not belong to same component

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

1. No. of provinces-

QUES- count no. of components in a graph

Approach-1 :

1. do a union on edge list using dsu
2. initialize ans=n
3. whenever u do a union, do ans--

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

Approach-2:

1. Do union of all edges
2. Traverse on parent array and when u find an element s.t i = parent[i] then cnt++

count all ultimate bosses ( which represents no. of unique elements in a parent array )

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

2. Min ops to make network connected-

Given- we can remove those edges from a component by removing which , that component still stays connected and edge this edge b/w some other pair of nodes
-----------------------------------------------

Ans = ( no. of components - 1 )
-----------------------------------------------

so, we will count these extra edges 

if (no. of extra edges) < ( no. of components - 1 ), then it is not possible to make n/w connected

else, it is possible

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

# counting extra edges-

while doing union, if the nodes have same ultimate parents, then their edge is an extra edge => cnt++ & don't do union of this edge

# counting no. of components-

see prvs ques
---------------------------------------------

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

3. Merge Accounts-⭐

1. consider different accounts as nodes (n nodes therefore)

2. now, map all emails to corresponding accounts (nodes)

3. if an email is already mapped to a prvs node, then update parent of curr node & do not map this mail

4. for answer, traverse through each email & check for ultimate parent of the node corr to this email

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

4. No. of islands 2-

Alter QUES- return vector storing count of no. of components in a graph while building a graph 
-------------
we will convert each cell of the matrix into a node, numbered from 0 to n-1

node for (r,c) = (r*m+c)

n: rows,  m: cols
--------------

1. take a query & see if it is an unmarked position then cnt++

2. if it is already marked 1 , then store ans for this query the same as old count & then skip 

3. if any neighbor is marked 1 & ultimate parents of both cells are different, then do join these 2 nodes & cnt--

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

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

5. Making a large island-⭐⭐

1. iterate and for each 1 union it with its adj 1s

2 check for all 0s the neighbors which are 1s & see the max count you can get by flipping that 0
    (by using size vector for the respective ultimate parents of each neighbor of a 0)

3. EDGE CASE- for storing ultimate parents of neighbors, use set as there can be a single component whose all 1s surround a 0

4. EDGE CASE- if grid contains all 1s , then loop for checking 0s won't be executed & we have to do some extra calculation to find ultimate parent and its size

5. max value you get after checking all 0s is the answer

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

6. Max Stones Removal-⭐

1. connect all stones which are in same row or same col

2. no. of stones that can be removed = sum of all (size of a connected component - 1) 
--------------------------------------------------------------
Approach-1: Thus we would find size of all ultimate parents and add (size-1) of each of them into ans

Approach-2: Also we can say step2 reduces to ans = ( no. of stones - no. of components )
--------------------------------------------------------------
We will take each row as a node and number them from 0 to R and then consider each col as further nodes and number them as j+R+1, where R is index of last row

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

1. mark rows & cols as consecutively numbered nodes

2. now for each stone , union its corresponding row & col 
    Also store the row node and col node in a map

3. count no. of ultimate parents from all nodes stored in map/set (= no. of connected components)

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

NOTE-

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