Last Updated: 20 Aug, 2021
Experiment On Atoms
Moderate
Asked in companies
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.
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
Approaches
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 :
- 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).
- Push the edges in the ‘GRAPH’.
- 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’.
- Create an array (say, ‘COLOR’) which will be used to store the color of every vertex present in the ‘GRAPH’.
- 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’)
- Update ‘VISITED[S]’ as TRUE and ‘COLOR[S]’ as 1.
- Create a queue (say, ‘Q’) and push ‘S’ into it.
- Run a loop until the queue does not become empty.
- 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’.
- If ‘VISITED[GRAPH[U][V]]’ is equal to ‘FALSE’
- Iterate over all the adjacent vertices of the ‘U’ (say, iterator ‘V’).
The approach is very similar to approach 1. We will be using DFS to check for a bipartite graph.
DFS(‘GRAPH’, ‘U’, ‘VISITED’, ‘COLOR’)
- Create a variable (say, ‘RES’) and initialize it as ‘TRUE’.
- 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 1.
- Update ‘COLOR[GRAPH[U][V]]’ as 1 - ‘COLOR[U]’.
- Call DFS on all adjacent vertices of ‘U’ and do bitwise ‘AND’ of it with ‘RES’.
- Else check if ‘COLOR[U]’ is equal to ‘COLOR[GRAPH[U][V]]’, return ‘FALSE’.
- Finally, return ‘RES’.
- If ‘VISITED[GRAPH[U][V]]’ is equal to ‘FALSE’