human
Check if there is a cycle with odd weight sum in an undirected graph | This function returns true if the current subpart of the forest is two colorable , else false ..
Assign first color to source.
Create a queue ( FIFO ) of vertex numbers and enqueue source vertex for BFS traversal.
Run while there are vertices in queue ( Similar to BFS ).
Find all non - colored adjacent vertices.
An edge from u to v exists and destination v is not colored.
Assign alternate color to this adjacent v of u.
An edge from u to v exists and destination v is colored with same color as u.
This function returns true if graph G [ V ] [ V ] is two colorable , else false.
Create a color array to store colors assigned to all veritces . Vertex number is used as index in this array . The value ' - 1' of colorArr [ i ] is used to indicate that no color is assigned to vertex ' i ' . The value 1 is used to indicate first color is assigned and value 0 indicates second color is assigned ..
As we are dealing with graph , the input might come as a forest , thus start coloring from a node and if true is returned we 'll know that   we successfully colored the subpart of our   forest and we start coloring again from a new   uncolored node. This way we cover the entire forest. .
Returns false if an odd cycle is present else true int info [ ] [ ] is the information about our graph int n is the number of nodes int m is the number of informations given to us.
Declaring adjacency list of a graph Here at max , we can encounter all the edges with even weight thus there will be 1 pseudo node for each edge.
For odd weight edges , we directly add it in our graph.
For even weight edges , we break it.
Entering a pseudo node between u -- - v.
Keeping a record of number of pseudo nodes inserted.
Making a new pseudo node for next time.
We pass number graph G [ ] [ ] and total number of node = actual number of nodes + number of pseudo nodes added ..
Driver function.
' n ' correspond to number of nodes in our graph while ' m ' correspond to the..."
How can the above be solved in Python?
 Give me a code to check if there is a cycle with odd weight sum in an undirected graph and the other steps required?
assistant
#Here is code to check if there is a cycle with odd weight sum in an undirected graph and the other steps required.
 def twoColorUtil ( G , src , N , colorArr ) :
	colorArr [ src ] = 1
	q = [ src ]
	while len ( q ) > 0 :
		u = q . pop ( 0 )
		for v in range ( 0 , len ( G [ u ] ) ) :
			if colorArr [ G [ u ] [ v ] ] == - 1 :
				colorArr [ G [ u ] [ v ] ] = 1 - colorArr [ u ]
				q . append ( G [ u ] [ v ] )
			elif colorArr [ G [ u ] [ v ] ] == colorArr [ u ] :
				return False
	return True
def twoColor ( G , N ) :
	colorArr = [ - 1 ] * N
	for i in range ( N ) :
		if colorArr [ i ] == - 1 :
			if twoColorUtil ( G , i , N , colorArr ) == False :
				return False
			return True
def isOddSum ( info , n , m ) :
	G = [ [ ] for i in range ( 2 * n ) ]
	pseudo , pseudo_count = n + 1 , 0
	for i in range ( 0 , m ) :
		if info [ i ] [ 2 ] % 2 == 1 :
			u , v = info [ i ] [ 0 ] , info [ i ] [ 1 ]
			G [ u ] . append ( v )
			G [ v ] . append ( u )
		else :
			u , v = info [ i ] [ 0 ] , info [ i ] [ 1 ]
			G [ u ] . append ( pseudo )
			G [ pseudo ] . append ( u )
			G [ v ] . append ( pseudo )
			G [ pseudo ] . append ( v )
			pseudo_count += 1
			pseudo += 1
	return twoColor ( G , n + pseudo_count )
if __name__ == " _ _ main _ _ " :
	n , m = 4 , 3
	info = [ [ 1 , 2 , 12 ] , [ 2 , 3 , 1 ] , [ 4 , 3 , 1 ] , [ 4 , 1 , 20 ] ]
	if isOddSum ( info , n , m ) == True :
		print ( " No " )
	else :
		print ( " Yes " )