Doctor Strange
Hard Accuracy: 54.56% Submissions: 1168 Points: 8

Kamar-taj is a place where "The Ancient One" trains people to protect earth from other dimensions.
The earth is protected by N sanctums, destroying any of it will lead to invasion on earth.
The sanctums are connected by M bridges.
Now , you being on dormammu's side , want to find the number of sanctum destroying which will disconnect the sanctums.

Example 1:

N = 5, M = 5
arr[] = {{1,2},{1,3},{3,2},{3,4},{5,4}}
Output : 2
1.Removing 1 will not make graph disconnected
2.Removing 2 will also not make 
graph disconnected(1--3--4--5).
3.Removing 3 makes graph disconnected 
(1--2 and 4--5).
4.Removing 4 makes graph disconnected 
(1--2--3--1 and 5).
5.Removing 5 also doesn't makes 
graph disconnected(3--1--2--3--4).
6. Therefore,there are two such vertices,
3 and 4,so the answer is 2.

Example 2:

Input : 
N = 2, M = 1 
arr[] = {{1, 2}}
Output : 0

Your Task:

This is a function problem. The input is already taken care of by the driver code. You only need to complete the function doctorStrange() that takes a number of nodes (N), a number of edges (M), a 2-D matrix that contains connection between nodes (graph), and return the number of sanctums when destroyed will disconnect other sanctums of Earth. 

Expected Time Complexity: O(N + M).
Expected Auxiliary Space: O(N + M).


1 ≤ n ≤ 30000
1 ≤ m ≤ 30000
1 ≤ u, v ≤ n

Click here to view old Disqus comments.

to report an issue on this page.




All Submissions

My Submissions:

Login to access your submissions.

Doctor Strange

Output Window