Experiment On Atoms

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in companies
AmazonAmazon

Problem statement

Professor Ninja is experimenting with atoms. He knows atoms consist of protons, electrons, and neutrons. His experiment is successful if he can separate interconnected protons and electrons to avoid the exhaustion of the atoms. Given the interconnections between electrons and protons, find whether the professor's experiment can be successful or not.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains two single space-separated integers, ‘N’ and ‘E’, representing the sum of electrons and protons and the number of interconnections, respectively.

The next ‘E’ lines will denote the interconnections between protons and electrons defined by two single space-separated integers ‘X' and 'Y', which signifies an interconnection between ‘X’ and ‘Y’.
Output Format : 
For each test case, return a single integer ‘1’ if they can be separated, else print ‘0’.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 2*10^3
1 <= E <= 10^5
1 <= X, Y <= N

Time Limit : 1 sec
Sample Input 1 :
1
4 3
1 2
2 3
2 4
Sample Output 1 :
1
Explanation For Sample Input 1 :
The interconnections will be :


There is no common interconnection between points 1, 3, and 4, so they can be divided into two sets: {1, 3, 4}, {2} where the first set can be of electrons, and the other can be of protons.
Sample Input 2 :
1
3 3
1 2
2 3
1 3
Sample Output 2 :
0
Explanation For Sample Input 2 :
The interconnections will be :


The above interconnections cannot be divided into two sets such that there one set is of electrons and the other is of protons.
Hint

Think of interconnections as a graph.

Approaches (2)
Breadth - First Search

The basic idea is to check whether the given interconnections are a bipartite graph or not. A bipartite graph is a graph in which the graph’s vertices can be divided into two independent sets, ‘U’ and ‘V’, such that for every edge (u, v), either u belongs to set ‘U’ and v belongs to set ‘V’ or vice-versa. They shouldn’t belong to the same set. A bipartite graph can be colored so that only two colors in total would be used,  where the neighbor vertices have different colors. Therefore we can assign colors to each vertex, and if at any point neighboring vertices have the same color, we return false.
 

Here is the algorithm :
 

  1. Create a graph (say, ‘GRAPH’) using the ‘EDGES’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
  2. Push the edges in the ‘GRAPH’.
  3. Create an array (say, ‘VISITED’) which will be used to mark all the visited vertices and initialize it with ‘FALSE’ for every vertex present in the ‘GRAPH’.
  4. Create an array (say, ‘COLOR’) which will be used to store the color of every vertex present in the ‘GRAPH’.
  5. Call the ‘BFS’ function, BFS(‘GRAPH’, ‘S’, ‘VISITED’, ‘COLOR’) for every unvisited vertex which will check for bipartite or not where ‘S’ is an unvisited vertex.

 

BFS(‘GRAPH’, ‘S’, ‘VISITED’, ‘COLOR’)

 

  1. Update ‘VISITED[S]’ as TRUE and ‘COLOR[S]’ as 1.
  2. Create a queue (say, ‘Q’) and push ‘S’ into it.
  3. Run a loop until the queue does not become empty.
  4. Create a variable (say, ‘U’) and store the front element of the queue in it and pop the element from the queue.
    • Iterate over all the adjacent vertices of the ‘U’ (say, iterator ‘V’).
      • If ‘VISITED[GRAPH[U][V]]’ is equal to ‘FALSE’
        • If ‘GRAPH[U][V]’ is equal to ‘U’ ( self - loop ), return ‘FALSE’.
        • Update ‘VISITED[GRAPH[U][V]]’ as ‘TRUE’.
        • Update ‘COLOR[GRAPH[U][V]]’ as 1 - ‘COLOR[U]’.
        • Push ‘GRAPH[U][V]’ into the queue.
      • Else check if ‘COLOR[U]’ is equal to ‘COLOR[GRAPH[U][V]]’, return ‘FALSE’.
Time Complexity

O(N + E), where ‘N’ is the sum of protons and electrons and ‘E’ is the number of interconnections.
 

We are traversing all the vertices only once by traversing all the edges using bfs. Therefore, the overall time complexity will be O(N + E).

Space Complexity

O(N + E), where ‘N’ is the sum of protons and electrons and ‘E’ is the number of interconnections.

 

For each vertex, we store its adjacent vertices, therefore storing the vertices in the form of a graph will require O(N + E) space. We also use queue (‘Q’) to do the bfs traversal, ‘COLOR’ array to store the color of vertex and ‘VISITED’ array which all require O(N) space. Therefore, the overall space complexity will be O(N + E).

Code Solution
(100% EXP penalty)
Experiment On Atoms
Full screen
Console