PROBLEM LINK:
Author: admin6
Tester: admin5
Editorialist: admin6
DIFFICULTY:
EASY
PREREQUISITES:
Graph
PROBLEM:
You are given three integers of M, N and Q. M denotes the number of nodes in graph , N denotes number of edges and Q denotes number of queries. For each query, you have to find number of nodes which are separated from graph .
QUICK EXPLANATION:
You are given a graph with N nodes and M edges. You can use either adjacency matrix or adjacency list to store graph. Now you are ready to answer the query.
Each query performed on graph denotes an edge to be cut off. In order to find the separated nodes you can use either depth-first search or breadth-first search approach.
Complexity of solution is O(NlogN).
DETAILED EXPLANATION
Prepare an adjacency list for graph of N nodes
and M edges. After that you can answer the query.
You have to find the edge to be cut off. Then count the nodes which are connected to that edge, are the nodes which are separated from graph after performing the query. Use breadth-first search approach to count the number of nodes. You can also use depth-first search, but in this problem it increases your execution time.
Complexity : O(NlogN)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.