42. Graphs-6 : MST, 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-

- MST gives set of edges, such that we connect all nodes in a network with min total cost

- For an MST to exist-
graph must be connected, undirected, weighted, has no cycles, has n-1 edges

- A graph can have multiple spanning trees. Out of all, one with min sum of all edge weights is called MST of the graph

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

# Prim's Algo-
(greedy)

time: O(ElogV)

- used to build mst of a graph, or find min sum of mst of graph

- Approach: build the tree by moving forward (at each step) with the node having cheapest cost 

------------------------------
- we use a min heap (to get min cost node at each step), a visited vector & a sum variable (storing min sum of final mst)
- If mst is asked, store parent for each node in the pq

- if min sum is asked, no need to store parent in pq
----------------------------- 

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

# Disjoint Set-⭐

- a custom data structure used for dynamic graphs (keeps changing their configuration)
- it gives 2 functionalities- finding parent of a node
                                         - joining 2 nodes by rank or size
- DSU is a forest of trees, such that each tree is a group of connected components in original graph which stores information of connectivity of that component nodes in original graph
- DSU trees are always acyclic
---------------
- At any step of graph changing, DSU tells, if 2 nodes belong to same component in O(1)

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

# 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 => height of tree (in terms of edges) rooted at this node

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

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

for each element in edge list: (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 can 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. Also, after path compression, rank is not changed, because it is rank and not height
-------

3. Why connect smaller to larger ?
- because whenever we connect A to B, then distance covered by nodes in A to reach ultimate parent increases
- 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 

----------------------------
- size array initialised with size of each element as 1
- we increase size in both cases, unlike union by rank.

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

# Note-

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

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

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

# Kruskal's Algo-

time: O(ElogE)

- uses greedy + DSU to build mst for a given graph
- we only join nodes belonging to different components, to avoid cycles in a MST, since nodes in same component if joined will eventually form a cycle which violate MST
-------------
1. sort all edges as per weight

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

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

1. Count no. of components in a graph-

Approach-1: time: O(V+E)

1. initialise ans = n (assume all nodes are disconnected at start)
2. Perform a DSU based union on nodes belonging to different components,
and whenever u do a union, do (ans--)

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

Approach-2:

1. Do union of all edges
2. Traverse on parent array and do cnt++ when, i = parent[i] 

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 add this edge b/w some other pair of nodes
---------------------------------------------
Approach:

- min no. of extra edges to be removed = ( no. of components - 1 ) 
- We will count extra edges & no. of components in the graph

- if, [ n(extra edges) < n(components)-1 ] => not possible to make n/w connected

- else, it is possible

1. Counting extra edges-

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

2. Counting no. of components- 
do union of entire graph & at last count ultimate parents in the parent vector

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

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

3. Accounts merge-⭐

1. consider different accounts as nodes 

2. now, map all emails to corresponding 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-II

QUES- return vector storing count of no. of components in a graph while building a graph 
-------------
Approach-

we will convert each cell of the matrix into a node (0 to n-1)

node for (i,j) = (i*r + j),   where: r = rows,  c = cols

- cnt here is no. of components in the grid at any time

- If for a query (x,y), it was already a land => ans is same as old cnt
- If it was not a land:
    1. mark it as a land and do cnt++
    2. connect all possible (disconnected) neighbours to this land and on each union decrease         the cnt 
---------------

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

5. Making a large island-⭐

Approach-
1. iterate for 1s and union them with adj 1s

2 Now, check for all 0s whose neighbours are 1s & see max count you can get by flipping that 0 (by using size vector for the respective ultimate parents of each neighbour of a 0)
---------------------

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

# 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
-----------------------

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

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 step 2 reduces to ans = ( no. of stones - no. of components )
---------------------------------------------
Instead of mapping a cell to a node, we will map a (row,col) combination to a node
We will take each row as a node and number them from 0 to R &
then consider each col as further nodes and number them as j+R+1, where R is index of last row

--------------------------------------------------------
Approach-2:

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