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:
Input:
N = 5, M = 5
arr[] = {{1,2},{1,3},{3,2},{3,4},{5,4}}
Output : 2
Explanation:
1.Removing 1 will not make graph disconnected
(2--3--4--5).
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).
 
Constraints:
1 ≤ n ≤ 30000
1 ≤ m ≤ 30000
1 ≤ u, v ≤ n

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3





class Solution:

    def doctorStrange (self,n, k, g) : 

        #Complete the function



Solutions:
import sys
sys.setrecursionlimit(10000)

class Solution:

	def dfs(self, adj, v, prev=-1):
		self.it[v] = self.time
		self.low[v] = self.time
		self.time += 1
		children = 0
		for w in adj[v]:
			if w == prev:
				continue
			if self.it[w] == -1:
				children += 1
				self.dfs(adj, w, v)
				self.low[v] = min(self.low[v], self.low[w])
				if self.low[w] >= self.it[v] and prev != -1:
					self.ans.add(v)
			else:
				self.low[v] = min(self.low[v], self.it[w])
		if children > 1 and prev == -1:
			self.ans.add(v)

	def doctorStrange(self, n, m, g):
		adj = [[] for _ in range(n)]
		for e in g:
			adj[e[0] - 1].append(e[1] - 1)
			adj[e[1] - 1].append(e[0] - 1)
		self.ans = set()
		self.time = 0
		self.low = [-1] * n
		self.it = [-1] * n
		for i in range(n):
			if self.it[i] == -1:
				self.dfs(adj, i)
		return len(self.ans)


from sys import setrecursionlimit
setrecursionlimit(100000)
tin = []
low = []
vis = []
time = 0

def dfs(graph, curr, parent, ans):
	global tin, low, vis, time
	vis[curr] = 1
	tin[curr] = time + 1
	low[curr] = time + 1
	time += 1
	ctr = 0
	for child in graph[curr]:
		if child == parent:
			continue
		if not vis[child]:
			dfs(graph, child, curr, ans)
			low[curr] = min(low[curr], low[child])
			if low[child] >= tin[curr] and parent != -1:
				ans[curr] = 1
			ctr += 1
		else:
			low[curr] = min(low[curr], tin[child])
	if parent == -1 and ctr > 1:
		ans[curr] = 1

class Solution:

	def doctorStrange(self, n, k, g):
		global tin, low, vis, time
		tin = [-1 for i in range(30005)]
		low = [-1 for i in range(30005)]
		vis = bytearray(30005)
		ans = bytearray(30005)
		graph = [[] for i in range(30005)]
		for i in g:
			(a, b) = i
			graph[a].append(b)
			graph[b].append(a)
		time = 0
		for i in range(30005):
			if not vis[i]:
				dfs(graph, i, -1, ans)
		ret = 0
		for i in range(30005):
			if ans[i]:
				ret += 1
		return ret


import sys
sys.setrecursionlimit(100000000)
time = 0

def articulationutil(graph, v, disc, low, parent, ans):
	global time
	disc[v] = time
	low[v] = time
	time += 1
	child = 0
	for i in graph[v]:
		if disc[i] == -1:
			child += 1
			parent[i] = v
			articulationutil(graph, i, disc, low, parent, ans)
			if parent[v] == -1 and child > 1:
				ans.append(v)
			if parent[v] != -1 and low[i] >= disc[v]:
				ans.append(v)
			low[v] = min(low[v], low[i])
		elif i != parent[v]:
			low[v] = min(low[v], disc[i])

def articulation(graph):
	disc = [-1] * len(graph)
	low = [-1] * len(graph)
	parent = [-1] * len(graph)
	ans = []
	articulationutil(graph, 1, disc, low, parent, ans)
	return len(set(ans))

class Solution:

	def doctorStrange(self, n, k, g):
		graph = [[] for i in range(n + 1)]
		for i in g:
			graph[i[0]].append(i[1])
			graph[i[1]].append(i[0])
		return articulation(graph)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, i, p, vis, graph, dis, low, l, ap):
		vis[i] = 1
		dis[i] = low[i] = l[0]
		l[0] += 1
		c = 0
		for j in graph[i]:
			if j == p:
				continue
			if vis[j] == 0:
				self.dfs(j, i, vis, graph, dis, low, l, ap)
				low[i] = min(low[i], low[j])
				if low[j] >= dis[i] and p != -1:
					ap.add(i)
				c += 1
			else:
				low[i] = min(low[i], dis[j])
		if c > 1 and p == -1:
			ap.add(i)

	def doctorStrange(self, n, k, g):
		adj = []
		for i in range(n):
			adj.append([])
		for i in g:
			adj[i[0] - 1].append(i[1] - 1)
			adj[i[1] - 1].append(i[0] - 1)
		l = [0]
		low = [-1] * n
		dis = [-1] * n
		vis = [0] * n
		ap = set()
		self.dfs(0, -1, vis, adj, dis, low, l, ap)
		ap = list(ap)
		ap.sort()
		return len(ap)