I was asked the following question in my recent onsite interview.\nGiven a list of pair of integers which denotes ```edges in the graph``` and another list of pair of integers which denotes ```enemy nodes in the graph```. You have to return a boolean array denoting ```if an edge can be added or not```. An edge should be added to the graph only when adding it doesn\'t make any of the enemy nodes connected.\n```\nSample Input:\nEnemy list: [[1,5], [1,4]]\nEdge list: [[0,1], [1,2], [3,4], [2,5], [2,3]]\nOutput: [True, True, True, False, False]\nExplanation: Edges [0,1], [1,2] and [3,4] can be added because no enemy nodes are connected till now. Hence, output is True for all of them. Now, adding [2,5] makes 1 and 5 connected which are enemy nodes, hence false. Similarly, adding [2,3] makes 1 and 4 connected which are enemies and hence output is false corresponding to edge [2,3]. \n\n```\nI coded the brute force approach which meant doing a dfs after addition of each edge and stored the enemy list in a map of set, which meant O(log V) time for each check of enemy list.\nSo, time complexity for each edge: \nO(V^2 * log V)

I was asked the following question in my recent onsite interview.\nGiven a list of pair of integers which denotes edges in the graph and another list of pair of