Check if there is a Cycle with Odd Weight Sum in an Undirected Graph.

✨Algorithm for solving the Problem

The solution is based on the rule, “If a graph has no odd length cycle, it must be Bipartite, meaning it can have two colors applied to it”. The goal is to convert the given problem into a simpler one. We just have to check whether the cycle is of odd length. To transform, we can follow the following algorithm:

• Make two edges of unity weight from all edges that are even weight.
   
• Make a single edge of unit weight out of all the odd weight edges.
   

For the first example given above, we can have the following diagram after applying the algorithm:

At first, the edges between 1 and 2 are broken into two parts. A pseudo node is attached to the vertex in the middle. We have broken this so that all the even weighted edges are considered twice. The odd weighted edges it is evaluated only once. To color our cycle, we have performed the steps mentioned above. All the edges are weighted unity. By using the two-color method, we encircle the whole graph.

Now using the two colors, the graph is modified. The cycle contains an even number of nodes, coloring the graph using two colors, resulting in no adjacent edges of the same color. If we had tried to color the odd numbers of advantages, two edges would have the same color. 

This is the desired outcome we need. So if we successfully make the colors of all adjacent edges different, then there will be no cycle in the graph with an even number of nodes. If any issue arises during the process arises, then we can neutralize it as we have an odd cycle in the graph.

✨Implementation in Java:

/* Java program to check if there is a cycle of total odd weight*/

import java.io.*;
import java.util.*;
class CodingNinjas
{

	/* If the current section of the forest is two colorable, this method returns true; otherwise, it returns false.*/
	static boolean twoColorUtil(Vector<Integer>[] G,int src, int N,int[] colorArr)
	{

		/* Assign first color to source*/
		colorArr[src] = 1;

		/* Create a queue (FIFO) of vertex numbers and enqueue source vertex for BFS traversal */
		Queue<Integer> q = new LinkedList<>();
		q.add(src);

		/* Run while there are vertices in the queue (Similar to BFS) */
		while (!q.isEmpty())
		{
			int u = q.peek();
			q.poll();

			/* Find all non-colored adjacent vertices*/
			for (int v = 0; v < G[u].size(); ++v)
			{

				/* An edge from u to v exists and destination v is not colored*/
				if (colorArr[G[u].elementAt(v)] == -1)
				{

					/* Assign an alternate color to this adjacent v of u */
					colorArr[G[u].elementAt(v)] = 1 - colorArr[u];
					q.add(G[u].elementAt(v));
				}

				/* An edge from u to v exists and destination v is colored with the same color as u */
				else if (colorArr[G[u].elementAt(v)] == colorArr[u])
				return false;
			}
		}
	return true;
	}

	/* This function returns true if graph G[V][V] is two colorable, else false */
	static boolean twoColor(Vector<Integer>[] G, int N)
	{

		/* Create a color array to store colors assigned to all vertices. Vertex number is used as an 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 the value 0 indicates the second color is assigned. */
		int[] colorArr = new int[N + 1];
		for (int i = 1; i <= N; ++i)
		colorArr[i] = -1;

		/* As we are dealing with a 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. */
		for (int i = 1; i <= N; i++)
		if (colorArr[i] == -1)
		if (twoColorUtil(G, i, N, colorArr) == false)
		return false;
		return true;
	}

	/* 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 information given to us*/
	static boolean isOddSum(int[][] info, int n, int m) 
	{
		Vector<Integer>[] G = new Vector[2 * n];
		for (int i = 0; i < 2 * n; i++)
		G[i] = new Vector<>();
		int pseudo = n + 1;
		int pseudo_count = 0;
		for (int i = 0; i < m; i++)
		{

			/* For odd weight edges, we directly add it in our graph */
			if (info[i][2] % 2 == 1)
			{
				int u = info[i][0];
				int v = info[i][1];
				G[u].add(v);
				G[v].add(u);
			}

			/* For even weight edges, we break it*/
			else
			{
				int u = info[i][0];
				int v = info[i][1];

				/* Entering a pseudo node between u---v*/
				G[u].add(pseudo);
				G[pseudo].add(u);
				G[v].add(pseudo);
				G[pseudo].add(v);

				/* Keeping a record of the number of pseudo nodes inserted */
				pseudo_count++;

				/* Making a new pseudo node for next time*/
				pseudo++;
			}
		}
	return twoColor(G, n + pseudo_count);
	}

		/* Driver Code*/
		public static void main(String[] args)
		{
			int n = 4, m = 3;
			int[][] info = { { 1, 2, 12 }, { 2, 3, 1 },
			{ 4, 3, 1 }, { 4, 1, 20 } };

			/* This function break the even weighted edges into two parts. Makes the adjacency representation of the graph and sends it for two colorings.*/
			if (isOddSum(info, n, m) == true)
			System.out.println("No");
			else
			System.out.println("Yes");
		}
}

🧬Output for the above code: 

No

Check out this problem - Subarray Sum Divisible By K

Frequently Asked Questions

How do you determine if a cycle exists in an undirected graph?

We will apply the DFS traversal for the chosen graph to determine whether or not there are cycles in the undirected graph. When we discover any nearby vertex u, such that u has already been visited and u is not the parent of vertex v, we know that vertex v has been called. One cycle is then found.

What kind of graph does not have an odd cycle?

 If a graph does not contain any cycles of odd length, it is said to be bipartite. A bizarre length cycle includes an odd number of vertices.

Self-loop—is it a cycle?

It is not referenced anywhere as being a cycle.

Can a cycle repeat its vertices?

A closed path is a cycle. These cannot have anything repeated (neither edges nor vertices). Remember that the only vertices in closed sequences that can repeat are the start and end vertices.

Conclusion

This article extensively discussed the ‘Check if there is a Cycle with Odd Weight Sum in an Undirected Graph’ problem statement. We have given the examples for a better understanding of the ‘Check if there is a Cycle with Odd Weight Sum in an Undirected Graph’ problem statement. Then we saw complexities related to the ‘Check if there is a Cycle with Odd Weight Sum in an Undirected Graph’ problem statement. We have also seen the Algorithms for solving the problem statement. Finally, we have implemented the code in the java platform.

Recommended Readings

• DFS Algorithm
• Detect cycle in an undirected graph

You can refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.
Happy Learning!