critical_graph_connection

critical_graph_connection.py

from collections import defaultdict

class Graph:
	def __init__(self):
		self.graph = defaultdict(list)

	def make_graph(self,n,connections):
		self.n=n
		for conn in connections:
			self.graph[conn[0]].append(conn[1])
			self.graph[conn[1]].append(conn[0])

	def add_conn(self,conn):
		self.graph[conn[0]].append(conn[1])
		self.graph[conn[1]].append(conn[0])

	def remove_conn(self,conn):
		self.graph[conn[0]].remove(conn[1])
		self.graph[conn[1]].remove(conn[0])
	

	def findConnectedComp(self):
		count = 0
		visited = set()
		for node in list(self.graph.keys()):
			if node not in visited:
				self.bfs(node,visited)
				count+=1
		return count

	# can use this as well
	def dfs(self,node,visited):
		visited.add(node)
		for neigh in self.graph[node]:
			if neigh not in visited:
				self.dfs(neigh,visited)
			
	def bfs(self,node,visited):
		queue = [node]
		while queue:
			curr = queue.pop(0)
			visited.add(curr)
			for neigh in self.graph[curr]:
				if neigh not in visited:
					queue.append(neigh)
			

def critial_nodes_in_graph(n,connections):
	graph = Graph()
	graph.make_graph(n,connections)
	out = []
	for conn in connections:
		graph.remove_conn(conn)
		comp = graph.findConnectedComp()
		if comp>1:
			out.append(conn[0])
		graph.add_conn(conn)
	return out



print (critial_nodes_in_graph(7,[[1,2],[1,3],[2,4],[3,4],[3,6],[6,7],[4,5]])) # expect [3,6,4]