Answer to Question #300539 in Python for Lucas

Question

Given an input undirected graph, write a program to check if the graph is two-edge connected or not. If the graph is not two-edge connected, print all the bridge edges. (Assume that the input graph is connected.)

Input Format: The input is a text file which describes an undirected graph. The first line of the file specifies n & m, the number of vertices and number of edges in the graph respectively. The next m lines specify the m edges of the graph, one line per edge. An edge is described by its end points. If the number of vertices is n, assume that the vertices of the graph are numbered (0,1,..n-1).Code is run in terminal as python3 main.py ./input.txt

Output Format: Print YES, if the input graph is two-edge connected, NO otherwise. If printing NO, print all the bridge edges in the graph.

Sample Input 1

(for the graph shown on the right):

8 10

0 1

1 2

0 3

3 4

3 6

4 6

5 4

5 6

7 6

5 7

Sample Output 1:

NO

1 2

0 1

0 3

Answer 1

class Graph:



	V = 0


	# Array of lists for Adjacency
	# List Representation
	adj = [[]]


	# Constructor
	def __init__(self, v):
		
		self.V = v
		self.adj = [[] for i in range(v)]


	# Function to add an edge into the graph
	def addEdge(self, v, w):
	
		self.adj[v - 1].append(w - 1)
		
		# Add w to v's list.
		self.adj[w - 1].append(v - 1)


	# Function to find if the graph is
	# 2 edge connected or not
	def twoEdge(self, v):


		# To store number of edges for
		# each node
		noOfEdges = [len(self.adj[i]) for i in range(v)]


		flag = True


		# Check the number of edges
		# connected to each node
		for i in range(v):
			if (noOfEdges[i] < 2):
				flag = False
				break
			
		# Print the result
		if (flag):
			print("Yes")
		else:
			print("No")
	
# Driver code
if __name__=="__main__":


	# Number of nodes and edges
	V = 8
	E = 10


	# input your numbers
	edges = [ [ 1, 2 ], [ 1, 8 ],
			[ 1, 6 ], [ 2, 3 ],
			[ 2, 4 ], [ 3, 7 ],
			[ 3, 4 ], [ 7, 5 ],
			[ 7, 6 ], [ 7, 8 ] ]


	g = Graph(V)


	# Adding the edges to graph
	for i in range(E):
		g.addEdge(edges[i][0],
				edges[i][1])
	
	# Function call
	g.twoEdge(V)