Given an undirected graph with N vertices and M edges, the task is to find the absolute difference Between the sum of degrees of odd degree nodes and even degree nodes in an undirected Graph.
Examples:
Input: N = 4, edges[][] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }
Output: 12
Explanation:
Below is the graph for the above information:
Node -> Degree
1 -> 3
2 -> 3
3 -> 3
4 -> 3
Sum of odd degree node = 3 + 3 + 3 + 3 = 12
Sum of even degree node = 0
Difference = 12Input: N = 5, edges[][] = { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 } }
Output: 4
Approach:
- For each vertex, the degree can be calculated by the length of the Adjacency List of the given graph at the corresponding vertex.
- Count the sum of degrees of odd degree nodes and even degree nodes and print the difference.
Below is the implementation of the above approach:
C++
// C++ implementation to print the// Difference Between sum of degrees// of odd degree nodes and even // degree nodes.#include <bits/stdc++.h>using namespace std;// Function to print the difference// Between sum of degrees of odd// degree nodes and even degree nodes.int OddEvenDegree(int N, int M, int edges[][2]){ // To store Adjacency List of // a Graph vector<int> Adj[N + 1]; int EvenSum = 0; int OddSum = 0; // Make Adjacency List for (int i = 0 ; i < M ; i++) { int x = edges[i][0]; int y = edges[i][1]; Adj[x].push_back(y); Adj[y].push_back(x); } // Traverse each vertex for (int i = 1; i <= N; i++) { // Find size of Adjacency List int x = Adj[i].size(); // If length of Adj[i] is // an odd number, add // length in OddSum if (x % 2 != 0) { OddSum += x; } else { // If length of Adj[i] is // an even number, add // length in EvenSum EvenSum += x; } } return abs(OddSum - EvenSum);}// Driver codeint main(){ // Vertices and Edges int N = 4, M = 6; // Edges int edges[M][2] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }; // Function Call cout<< OddEvenDegree(N, M, edges); return 0;} |
Java
// Java implementation to print the// difference between sum of degrees// of odd degree nodes and even // degree nodes.import java.util.*;class GFG{// Function to print the difference// between sum of degrees of odd// degree nodes and even degree nodes.static int OddEvenDegree(int N, int M, int edges[][]){ // To store adjacency list // of a graph @SuppressWarnings("unchecked") Vector<Integer> []Adj = new Vector[N + 1]; for(int i = 0; i < N + 1; i++) { Adj[i] = new Vector<Integer>(); } int EvenSum = 0; int OddSum = 0; // Make adjacency list for(int i = 0; i < M; i++) { int x = edges[i][0]; int y = edges[i][1]; Adj[x].add(y); Adj[y].add(x); } // Traverse each vertex for(int i = 1; i <= N; i++) { // Find size of adjacency list int x = Adj[i].size(); // If length of Adj[i] is // an odd number, add // length in OddSum if (x % 2 != 0) { OddSum += x; } else { // If length of Adj[i] is // an even number, add // length in EvenSum EvenSum += x; } } return Math.abs(OddSum - EvenSum);}// Driver codepublic static void main(String[] args){ // Vertices and edges int N = 4, M = 6; // Edges int edges[][] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }; // Function call System.out.print(OddEvenDegree(N, M, edges));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation to print the# Difference Between sum of degrees# of odd degree nodes and even # degree nodes.# Function to print the difference# Between sum of degrees of odd# degree nodes and even degree nodes.def OddEvenDegree(N, M, edges): # To store Adjacency # List of a Graph Adj = [[] for i in range(N + 1)] EvenSum = 0; OddSum = 0; # Make Adjacency List for i in range(M): x = edges[i][0]; y = edges[i][1]; Adj[x].append(y); Adj[y].append(x); # Traverse each vertex for i in range(1, N + 1): # Find size of # Adjacency List x = len(Adj[i]) # If length of Adj[i] is # an odd number, add # length in OddSum if (x % 2 != 0): OddSum += x; else: # If length of Adj[i] is # an even number, add # length in EvenSum EvenSum += x; return abs(OddSum - EvenSum);# Driver codeif __name__ == "__main__": # Vertices and Edges N = 4 M = 6 # Edges edges = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] # Function Call print(OddEvenDegree(N, M, edges));# This code is contributed by rutvik_56 |
C#
// C# implementation to print the// difference between sum of degrees// of odd degree nodes and even // degree nodes.using System;using System.Collections.Generic;class GFG{// Function to print the difference// between sum of degrees of odd// degree nodes and even degree nodes.static int OddEvenDegree(int N, int M, int [,]edges){ // To store adjacency list // of a graph List<int> []Adj = new List<int>[N + 1]; for(int i = 0; i < N + 1; i++) { Adj[i] = new List<int>(); } int EvenSum = 0; int OddSum = 0; // Make adjacency list for(int i = 0; i < M; i++) { int x = edges[i, 0]; int y = edges[i, 1]; Adj[x].Add(y); Adj[y].Add(x); } // Traverse each vertex for(int i = 1; i <= N; i++) { // Find size of adjacency list int x = Adj[i].Count; // If length of Adj[i] is // an odd number, add // length in OddSum if (x % 2 != 0) { OddSum += x; } else { // If length of Adj[i] is // an even number, add // length in EvenSum EvenSum += x; } } return Math.Abs(OddSum - EvenSum);}// Driver codepublic static void Main(String[] args){ // Vertices and edges int N = 4, M = 6; // Edges int [,]edges = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}; // Function call Console.Write(OddEvenDegree(N, M, edges));}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation to print the// Difference Between sum of degrees// of odd degree nodes and even // degree nodes.// Function to print the difference// Between sum of degrees of odd// degree nodes and even degree nodes.function OddEvenDegree(N, M, edges){ // To store Adjacency List of // a Graph var Adj = Array.from(Array(N+1), ()=>Array()); var EvenSum = 0; var OddSum = 0; // Make Adjacency List for (var i = 0 ; i < M ; i++) { var x = edges[i][0]; var y = edges[i][1]; Adj[x].push(y); Adj[y].push(x); } // Traverse each vertex for (var i = 1; i <= N; i++) { // Find size of Adjacency List var x = Adj[i].length; // If length of Adj[i] is // an odd number, add // length in OddSum if (x % 2 != 0) { OddSum += x; } else { // If length of Adj[i] is // an even number, add // length in EvenSum EvenSum += x; } } return Math.abs(OddSum - EvenSum);}// Driver code// Vertices and Edgesvar N = 4, M = 6;// Edgesvar edges = [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ];// Function Calldocument.write( OddEvenDegree(N, M, edges));</script> |
Output
12
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/difference-between-sum-of-degrees-of-odd-and-even-degree-nodes-in-an-undirected-graph/ […]
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/difference-between-sum-of-degrees-of-odd-and-even-degree-nodes-in-an-undirected-graph/ […]