Good Bad Graph

APPROACH : 
 

• First, we will add the given edges to the graph for each operation.
• Then we will traverse the graph and find all the connected components.
• After that, we will iterate through every connected component to check whether it is good or bad.
• We will perform these steps for every operation.
• Then, we will print the absolute difference between the total good and bad components after each operation.

ALGORITHM :
 

• Initialize the ‘adj’ matrix of size ‘N’.
• Initialize the empty ‘ans’ array which we have to return at the end.
• For every operation:
  • Initialize an integer variable ‘cnt’ with the value zero.
  • Initialize the integers  ‘p’, ‘q’ denoting the cities to which we have to connect.
  • Initialize the ‘vis’ array of length ‘N + 1’ and set all its values to zero.
  • Add vertices ‘p’ and ‘q’ if not already added in the ‘adj’ matrix.
  • We will iterate from ‘i = 1’ till ‘i <= N’:
    • If ‘vis[ i ]’ == 0 :
      • Call dfs which will find all the cities which are connected to ‘ith’ cities and mark them visited.
  • Count all the good and bad connected components.
  • Update the ‘cnt’ with the absolute difference between the good and bad components.
  • Insert the ‘cnt’ to ‘ans’ array.
• Return ‘ans’;

APPROACH : 

• For each operation, we have to check how our graph is changing if we add some edge,  when we are connecting an edge we first need to check if the first city is connected to the second city if they are connected we don't need to do anything as they are already connected otherwise we will create an edge between both the node with this we will be merging two connected components and creating a single connected component since this is basically DSU itself so we will use DSU and now update the count of the good and bad component after every operation.

ALGORITHM :
 

• Initialize the ‘adj’ matrix of size ‘N’.
• Initialize the DSU of length ‘N’.
• Initialize the empty ‘ans’ array which we have to return at the end.
• Initialize the integer ‘cnt_good’ and ‘cnt_bad’  with the value zero.
• For every operation:
  • Initialize an integer variable ‘ans’ with the value zero.
  • Initialize an integer variable ‘cnt’ with the value zero.
  • Initialize the integers  ‘p’, ‘q’ denoting the city which we have to connect
  • Call ‘merge( ‘p’ , ‘q’ )’ function which will merge city ‘p’ and city ‘q’ and inside the merge function, first decrease the count of good or bad components where ‘p’  belongs to by one and similarly for ‘q’, and increase the count of good or bad component where final connected component (‘p’+’q’) belongs to.
  • Update the ‘cnt’ with the absolute difference between the cnt_good and cnt_bad value.
  • Insert the ‘cnt’ to ‘ans’ array.
  • Return ‘ans’;