Good Bad Graph

Hard
0/120
Average time to solve is 40m
profile
Contributed by
0 upvote
Asked in companies
OlaTata Consultancy Services (TCS)

Problem statement

There are ‘N’ cities in ninja Kingdom and Mayer of the city wants to connect all the cities using roads by performing the following operations ‘N - 1’ times. Initially, there are no edges between any cities.

At every operation, you are given two cities, ‘A’ and ‘B’, and you have to connect the city if they are not already connected.

Connected component is that part of the graph in which we have at least two city and we can reach one city to other cities and no two connected components share a common city.

After every input edge, there can be multiple connected components.

Component is good if the number of cities of that component is even; otherwise, it is a bad component.

You need to find the absolute difference between total good and bad components after adding each edge.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case contains the value ‘N’, denoting the number of cities.

Following ‘N - 1’ lines contain two space-separated integers, ‘u’ and ‘v’, which we have to connect the city ‘u’ and ‘v’.
Output format : 
For each test case, return an array of size ‘N - 1’, where the ‘i’th ( 0 <= i < N - 1 )  value represents the absolute difference between total good and bad components after adding the ‘ith’ edge.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10

2 <= N <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
5 
1 2
3 4
2 5
2 3
3
1 2
2 3
Sample Output 1 :
1 2 0 1
1 1
Explanation Of Sample Input 1 :
For test case 1, 
       After adding the first edge:
                    we have only one connected component, i.e. (1, 2).
                    Total good component = 1 ( 1, 2 ).
                    Total bad component = 0.
          After adding the second edge:
                    we have two connected components, i.e., (1, 2) and (3, 4).
                    Total good component = 2 ( ( 1, 2 ) , ( 3, 4 ) ).
                    Total bad component = 0. 
          After adding the third edge:
                    we have two connected components, i.e., (1, 2, 5) and (3, 4).
                    Total good component = 1 ( 3, 4 ).
                    Total bad component = 1 ( 1, 2, 5 ). 
          After adding forth edge:
                    we have only one connected component, i.e., (1, 2, 3, 4, 5).
                    Total good component = 0.
                    Total bad component = 1 ( 1, 2, 3, 4, 5 ). 


For test case 2,
       After adding the first edge:
                    we have only one connected component, i.e. (1, 2).
                    Total good component = 1 ( 1, 2 ).
                    Total bad component = 0.
          After adding the second edge:
                    we have only one connected component, i.e. (1, 2, 3).
                    Total good component = 0.
                    Total bad component = 1 ( 1, 2, 3 ).
Sample Input 2 :
2
5
1 2
1 3
1 4
1 5
2
1 2
Sample Output 2 :
1 1 1 1
1
Hint

 Try to check for all operations independently

Approaches (2)
Brute Force

 

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’;
Time Complexity

O( N * N ), where ‘N’ is the total number of cities.

 

After every operation, we will check the entire graph to find the connected component the time to find all the connected components is O(N), and there are total ‘N’ operations, so the overall time complexity is O( N * N ).

Space Complexity

O( N ).

 

We are storing all input edges and the stack space used is of order O(N) , so the overall space complexity is O( N ).

 

Code Solution
(100% EXP penalty)
Good Bad Graph
Full screen
Console