Given an undirected connected graph with V vertices and adjacency list adj. You are required to find all the vertices removing which (and edges through it) disconnects the graph into 2 or more components.
Note: Indexing is zero-based i.e nodes numbering from (0 to V-1). There might be loops present in the graph.
Example 1:
Input:
Output:{1,4}
Explanation: Removing the vertex 1 will
discconect the graph as-
Removing the vertex 4 will disconnect the
graph as-
 
Your Task:
You don't need to read or print anything. Your task is to complete the function articulationPoints() which takes V and adj as input parameters and returns a list containing all the vertices removing which turn the graph into two or more disconnected components in sorted order. If there are no such vertices then returns a list containing -1.
 
Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)
 
Constraints:
1 ≤ V ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



import sys

sys.setrecursionlimit(10**6)



class Solution:

    

    #Function to return Breadth First Traversal of given graph.

    def articulationPoints(self, V, adj):

        # code here

Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
INV = 1000000000.0

class Solution:

	def articulationPoints(self, V, adj):

		def _solve(u, par):
			nonlocal cur
			cur += 1
			disc[u] = low[u] = cur
			children = 0
			for v in adj[u]:
				if v == par:
					continue
				if disc[v] == INV:
					_solve(v, u)
					children += 1
					low[u] = min(low[u], low[v])
					if u > 0 and low[v] >= disc[u] or (u == 0 and children > 1):
						ans[u] = True
				else:
					low[u] = min(low[u], disc[v])
		(disc, low, ans) = ([INV] * V, [INV] * V, [False] * V)
		cur = -1
		_solve(0, 0)
		ret = [i for (i, v) in enumerate(ans) if v]
		return ret if ret else [-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, node, parent, i, visited, tis, ltis, adj, res):
		(visited[node], tis[node], ltis[node]) = (True, i, i)
		children = 0
		for adjNode in adj[node]:
			if not visited[adjNode]:
				self.dfs(adjNode, node, i + 1, visited, tis, ltis, adj, res)
				if ltis[adjNode] < ltis[node]:
					ltis[node] = ltis[adjNode]
				if ltis[adjNode] >= tis[node] and parent != -1:
					res.add(node)
				children += 1
			elif adjNode != parent:
				if tis[adjNode] < ltis[node]:
					ltis[node] = tis[adjNode]
		if children > 1 and parent == -1:
			res.add(node)

	def articulationPoints(self, V, adj):
		(res, visited, tis, ltis) = (set(), [False] * V, [0] * V, [0] * V)
		self.dfs(0, -1, 1, visited, tis, ltis, adj, res)
		if res:
			res = list(res)
			res.sort()
			return res
		return [-1]


import sys
from collections import *
sys.setrecursionlimit(10 ** 6)

class Solution:

	def articulationPoints(self, V, adj):
		graph = defaultdict(list)
		for i in range(V):
			for a in adj[i]:
				graph[i].append(a)
		vis = [False] * V
		expectedtime = [None] * V
		actualtime = [None] * V
		res = set()
		time = 0

		def dfs(node, parent):
			nonlocal time
			vis[node] = True
			expectedtime[node] = time
			actualtime[node] = time
			time += 1
			child = 0
			for adja in graph[node]:
				if adja == parent:
					continue
				if not vis[adja]:
					dfs(adja, node)
					actualtime[node] = min(actualtime[node], actualtime[adja])
					if actualtime[adja] >= expectedtime[node] and parent != None:
						res.add(node)
					child += 1
				else:
					actualtime[node] = min(actualtime[node], expectedtime[adja])
			if parent == None and child > 1:
				res.add(node)
		for i in range(V):
			if not vis[i]:
				dfs(i, None)
		return sorted(list(res)) if res else [-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, arr, u, par, l, d, vis, ap, time):
		d[u] = l[u] = time
		time += 1
		ch = 0
		vis[u] = 1
		for v in arr[u]:
			if vis[v] == 0:
				ch += 1
				self.dfs(arr, v, u, l, d, vis, ap, time)
				l[u] = min(l[u], l[v])
				if par == -1 and ch > 1:
					ap.add(u)
				elif par != -1 and l[v] >= d[u]:
					ap.add(u)
			elif par != v and u != v:
				l[u] = min(l[u], d[v])

	def articulationPoints(self, V, arr):
		vis = [0] * V
		ap = set()
		l = [0] * V
		d = [0] * V
		time = 0
		for i in range(V):
			if vis[i] == 0:
				self.dfs(arr, i, -1, l, d, vis, ap, time)
		vec = list(ap)
		if len(vec) == 0:
			vec.append(-1)
		return sorted(vec)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def __init__(self):
		self.discI = 0
		self.rootSubtrees = 0

	def articulationPoints(self, V, adj):
		discL = [None] * V
		low = [None] * V
		visited = set()
		aps = set()
		self.dfs(0, adj, low, discL, -1, visited, aps)
		if len(aps) == 0:
			return [-1]
		return sorted(list(aps))

	def dfs(self, node, adj, low, discL, parent, visited, aps):
		if node in visited:
			return discL[node]
		discL[node] = self.discI
		low[node] = self.discI
		discL[node] = self.discI
		self.discI += 1
		visited.add(node)
		for child in adj[node]:
			if parent != child and node != child:
				if child not in visited:
					childLow = self.dfs(child, adj, low, discL, node, visited, aps)
					if parent == -1:
						self.rootSubtrees += 1
						if self.rootSubtrees >= 2:
							aps.add(node)
					elif childLow >= discL[node]:
						aps.add(node)
				else:
					childLow = discL[child]
				low[node] = min(low[node], childLow)
		return low[node]


import sys
sys.setrecursionlimit(10 ** 6)
from collections import *

class Solution:

	def articulationPoints(self, V, adj):

		def traverse(curr, parent):
			nonlocal parentCount, counter
			visited.add(curr)
			points = set()
			for (index, i) in enumerate(adj[curr]):
				if i != parent:
					if i in visited:
						points.add(i)
					else:
						if curr == src:
							parentCount += 1
						counter += 1
						low[i] = counter
						disc[i] = counter
						traverse(i, curr)
						points.add(i)
						if curr != src and disc[curr] <= low[i]:
							articulationPoints.add(curr)
			if len(points) > 0:
				for x in points:
					low[curr] = min(low[curr], low[x])
		articulationPoints = set()
		visited = set()
		parentCount = 0
		counter = 0
		disc = dict()
		low = dict()
		k = 0
		src = k
		disc[k] = 0
		low[k] = 0
		traverse(k, -1)
		if parentCount > 1:
			articulationPoints.add(k)
		res = list(articulationPoints)
		res.sort()
		if len(res) > 0:
			return res
		return [-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def articulationPoints(self, V, adj):

		def dfs(node, par, low, real, vis, ans):
			nonlocal timer
			timer += 1
			(low[node], real[node]) = (timer, timer)
			vis[node] = 1
			child = 0
			for i in adj[node]:
				if i == par:
					continue
				if not vis[i]:
					dfs(i, node, low, real, vis, ans)
					low[node] = min(low[node], low[i])
					if low[i] >= real[node] and par != -1:
						ans.add(node)
					child += 1
				else:
					low[node] = min(low[node], real[i])
			if child > 1 and par == -1:
				ans.add(node)
		timer = 0
		low = [0 for i in range(V)]
		real = [0 for i in range(V)]
		vis = [0 for i in range(V)]
		ans = set()
		for i in range(V):
			if not vis[i]:
				dfs(i, -1, low, real, vis, ans)
		if not ans:
			return [-1]
		return sorted(list(ans))


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, node, parent, adj, vis, tin, low, mark, timer):
		vis[node] = 1
		tin[node] = timer
		low[node] = timer
		timer += 1
		child = 0
		for adjNode in adj[node]:
			if adjNode == parent:
				continue
			if not vis[adjNode]:
				Solution.dfs(self, adjNode, node, adj, vis, tin, low, mark, timer)
				low[node] = min(low[node], low[adjNode])
				if tin[node] <= low[adjNode] and parent != -1:
					mark[node] = 1
				child += 1
			else:
				low[node] = min(low[node], tin[adjNode])
		if child > 1 and parent == -1:
			mark[node] = 1

	def articulationPoints(self, V, adj):
		vis = [0] * V
		tin = [0] * V
		low = [0] * V
		mark = [0] * V
		timer = 1
		for i in range(V):
			if not vis[i]:
				Solution.dfs(self, i, -1, adj, vis, tin, low, mark, timer)
		ans = []
		for i in range(V):
			if mark[i] == 1:
				ans.append(i)
		if len(ans) == 0:
			return [-1]
		return ans


import sys
sys.setrecursionlimit(10 ** 6)
from math import inf

class Solution:

	def articulationPoints(self, V, adj):
		visited = [0] * V
		tin = [inf] * V
		low = [inf] * V
		mark = set()
		timer = 1

		def dfs(node, par):
			nonlocal timer
			visited[node] = 1
			tin[node] = low[node] = timer
			timer += 1
			child = 0
			for each in adj[node]:
				if not visited[each]:
					dfs(each, node)
					low[node] = min(low[node], low[each])
					if low[each] >= tin[node] and par != -1:
						mark.add(node)
					child += 1
				else:
					low[node] = min(low[node], tin[each])
			if child > 1 and par == -1:
				mark.add(node)
		dfs(0, -1)
		return sorted(list(mark)) if mark else [-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	class Graph:

		def __init__(self, V, adj):
			self.n = V
			self.visited = [False for _ in range(self.n)]
			self.depth = [0 for _ in range(self.n)]
			self.low = [0 for _ in range(self.n)]
			self.articulationPoints = []
			self.counter = 0
			self.adjList = adj

	def DFS(self, G, vertex, parent, root):
		G.visited[vertex] = True
		G.depth[vertex] = G.counter
		G.low[vertex] = G.counter
		G.counter += 1
		children = 0
		for neighbour in G.adjList[vertex]:
			if G.visited[neighbour] == False:
				children += 1
				self.DFS(G, neighbour, vertex, root)
				G.low[vertex] = min(G.low[vertex], G.low[neighbour])
				if vertex == root and children > 1:
					if vertex not in G.articulationPoints:
						G.articulationPoints.append(vertex)
				if G.low[neighbour] >= G.depth[vertex]:
					if vertex != root:
						if vertex not in G.articulationPoints:
							G.articulationPoints.append(vertex)
			elif neighbour != parent:
				G.low[vertex] = min(G.low[vertex], G.depth[neighbour])

	def articulationPoints(self, V, adj):
		G = self.Graph(V, adj)
		for v in range(G.n):
			if G.visited[v] == False:
				self.DFS(G, v, None, v)
		G.articulationPoints.sort()
		if len(G.articulationPoints):
			return G.articulationPoints
		return [-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def articulationPoints(self, V, adj):
		parent = [-1] * (V + 1)
		disc = [-1] * (V + 1)
		low = [-1] * (V + 1)
		ap = [0] * (V + 1)
		time = 1

		def find_AP_util(curr_node, disc, low, parent, time, ap):
			disc[curr_node] = time
			low[curr_node] = time
			child = 0
			time += 1
			for i in adj[curr_node]:
				if disc[i] == -1:
					parent[i] = i
					child += 1
					find_AP_util(i, disc, low, parent, time, ap)
					low[curr_node] = min(low[curr_node], low[i])
					if parent[curr_node] == -1 and child > 1:
						ap[curr_node] = 1
					if parent[curr_node] != -1 and low[i] >= disc[curr_node]:
						ap[curr_node] = 1
				if parent[curr_node] != i:
					low[curr_node] = min(low[curr_node], disc[i])
		for i in range(V):
			if disc[i] == -1:
				find_AP_util(i, disc, low, parent, time, ap)
				time = 1
		x = []
		for i in range(V):
			if ap[i] == 1:
				x.append(i)
		if len(x) == 0:
			x = [-1] * 1
		return x


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, node, parent, timer, disc, low, vis, adj, ans):
		vis.add(node)
		disc[node] = low[node] = timer
		timer += 1
		child = 0
		for nbr in adj[node]:
			if nbr == parent:
				continue
			if nbr not in vis:
				self.dfs(nbr, node, timer, disc, low, vis, adj, ans)
				low[node] = min(low[node], low[nbr])
				if low[nbr] >= disc[node] and parent != -1:
					ans[node] = True
				child += 1
			else:
				low[node] = min(low[node], disc[nbr])
		if parent == -1 and child > 1:
			ans[node] = True

	def articulationPoints(self, V, adj):
		timer = 0
		disc = [-1] * V
		low = [-1] * V
		parent = -1
		vis = set()
		artPoint = [False] * V
		for i in range(V):
			if i not in vis:
				self.dfs(i, parent, timer, disc, low, vis, adj, artPoint)
		ans = []
		for i in range(V):
			if artPoint[i] == True:
				ans.append(i)
		if not ans:
			return [-1]
		return ans


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def articulationPoints(self, V, adj):

		def dfs(sv, parent, c):
			visited[sv] = 1
			time[sv] = low[sv] = c
			c += 1
			child = 0
			for u in adj[sv]:
				if u == parent:
					continue
				if visited[u] == 0:
					dfs(u, sv, c)
					low[sv] = min(low[sv], low[u])
					if low[u] >= time[sv] and parent != -1:
						mark[sv] = 1
					child += 1
				else:
					low[sv] = min(low[sv], time[u])
				if child > 1 and parent == -1:
					mark[sv] = 1
		time = [0 for i in range(V)]
		low = [0 for i in range(V)]
		visited = [0 for i in range(V)]
		mark = [0 for i in range(V)]
		c = 1
		for i in range(V):
			if visited[i] == 0:
				dfs(i, -1, c)
		ans = []
		for i in range(V):
			if mark[i]:
				ans.append(i)
		if len(ans) == 0:
			return [-1]
		return ans


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def articulationPoints(self, V, adj):
		n = V
		timeOfVisit = [-1 for i in range(n)]
		lowestTimeOfVisit = [float('inf') for i in range(n)]
		visited = set()
		ans = set()

		def dfs(node, parent, time):
			visited.add(node)
			timeOfVisit[node] = time
			lowestTimeOfVisit[node] = time
			disconnectedChilds = 0
			for neib in adj[node]:
				if neib not in visited:
					dfs(neib, node, time + 1)
					disconnectedChilds += 1
					lowestTimeOfVisit[node] = min(lowestTimeOfVisit[node], lowestTimeOfVisit[neib])
					if lowestTimeOfVisit[neib] >= timeOfVisit[node] and parent != -1:
						ans.add(node)
				else:
					lowestTimeOfVisit[node] = min(lowestTimeOfVisit[node], timeOfVisit[neib])
			if parent == -1 and disconnectedChilds > 1:
				ans.add(node)
		dfs(0, -1, 0)
		ans = sorted(list(ans))
		return ans if ans else [-1]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def articulationPoints(self, n, connections):
		result = set()
		visited = [False] * n
		tIn = [0] * n
		lowIn = [0] * n
		self.timer = 1

		def dfs(node, parent):
			visited[node] = True
			tIn[node] = lowIn[node] = self.timer
			self.timer += 1
			child = 0
			for adj in connections[node]:
				if adj == parent:
					continue
				if visited[adj] == False:
					dfs(adj, node)
					lowIn[node] = min(lowIn[node], lowIn[adj])
					if lowIn[adj] >= tIn[node] and parent != -1:
						result.add(node)
					child += 1
				else:
					lowIn[node] = min(lowIn[node], tIn[adj])
			if child > 1 and parent == -1:
				result.add(node)
		for i in range(n):
			if not visited[i]:
				dfs(i, -1)
		return [-1] if len(result) == 0 else sorted(list(result))


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, adj, node, parent):
		self.vis[node] = 1
		(self.discovery[node], self.low[node]) = (self.t, self.t)
		self.t += 1
		child = 0
		for i in adj[node]:
			if i == parent:
				continue
			if not self.vis[i]:
				self.dfs(adj, i, node)
				self.low[node] = min(self.low[i], self.low[node])
				if self.low[i] >= self.discovery[node] and parent != -1:
					self.res[node] = 1
				child += 1
			else:
				self.low[node] = min(self.low[node], self.discovery[i])
		if parent == -1 and child > 1:
			self.res[node] = 1

	def articulationPoints(self, V, adj):
		self.res = {}
		self.discovery = [-1 for i in range(V)]
		self.low = [float('inf') for i in range(V)]
		self.vis = [0 for i in range(V)]
		self.t = 0
		self.dfs(adj, 0, -1)
		if not self.res:
			return [-1]
		return sorted(list(self.res.keys()))


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def articulationPoints(self, V, adj):
		visited = set()
		mark = [0 for i in range(V)]
		time = [1]
		tin = [0 for i in range(V)]
		low = [0 for i in range(V)]

		def dfs(node, parent):
			visited.add(node)
			tin[node] = time[0]
			low[node] = time[0]
			time[0] += 1
			child = [0]
			for nei in adj[node]:
				if nei == parent:
					continue
				elif nei not in visited:
					dfs(nei, node)
					low[node] = min(low[node], low[nei])
					if low[nei] >= tin[node] and parent != -1:
						mark[node] = 1
					child[0] += 1
				else:
					low[node] = min(low[node], tin[nei])
			if child[0] > 1 and parent == -1:
				mark[node] = 1
			return
		for i in range(V):
			if i not in visited:
				dfs(i, -1)
		ans = []
		for i in range(len(mark)):
			if mark[i] == 1:
				ans.append(i)
		if len(ans) == 0:
			return [-1]
		return ans


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:
	timer = 1

	def articulationPoints(self, v, adj):

		def dfs(node, parent, vis, tin, low, mark, adj):
			vis[node] = 1
			tin[node] = low[node] = self.timer
			self.timer += 1
			child = 0
			for it in adj[node]:
				if it == parent:
					continue
				if vis[it] == 0:
					dfs(it, node, vis, tin, low, mark, adj)
					low[node] = min(low[it], low[node])
					if low[it] >= tin[node] and parent != -1:
						mark[node] = 1
					child += 1
				else:
					low[node] = min(low[node], tin[it])
			if child > 1 and parent == -1:
				mark[node] = 1
		vis = [0] * v
		tin = [0] * v
		low = [0] * v
		mark = [0] * v
		for i in range(v):
			if vis[i] == 0:
				dfs(i, -1, vis, tin, low, mark, adj)
		ans = []
		for i in range(v):
			if mark[i] == 1:
				ans.append(i)
		if len(ans) == 0:
			return [-1]
		return ans


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def articulationPoints(self, V, adj):
		low = [float('inf') for i in range(V)]
		parent = [-1 for i in range(V)]
		visited = [0 for i in range(V)]
		disc = [float('inf') for i in range(V)]
		ap = [0] * V
		time = 0

		def dfs(u, time):
			low[u] = time
			disc[u] = time
			children = 0
			visited[u] = 1
			time += 1
			for v in adj[u]:
				if visited[v] == 0:
					parent[v] = u
					children += 1
					dfs(v, time)
					low[u] = min(low[u], low[v])
					if parent[u] != -1 and low[v] >= disc[u]:
						ap[u] = 1
					if parent[u] == -1 and children > 1:
						ap[u] = 1
				elif v != parent[u]:
					low[u] = min(low[u], disc[v])
		for u in range(V):
			if visited[u] == 0:
				dfs(u, time)
		arti_points = []
		for i in range(len(ap)):
			if ap[i] == 1:
				arti_points.append(i)
		if len(arti_points) == 0:
			return [-1]
		return arti_points