Find count of pair of nodes at even distance
Given a connected acyclic graph with N nodes and N-1 edges, find out the pair of nodes that are at even distance from each other.
Examples:
Input: 3 1 2 2 3 Output: 1 Explanation: 1 / 2 / 3 Input: 5 1 2 2 3 1 4 4 5 Output: 4
Approach:
- Assume a graph is having 6 levels (0 to 5) level 0, 2, 4 are at even distance but level 1, 3, 5 are also at even distance as their difference is 2 which is even so we have to take care of both the conditions i.e count both levels even and odd.
- The given problem can be solved by performing dfs traversal
- Choose any source node as root and perform dfs traversal and maintain the visited
array for performing dfs and dist array to calculate distance from the root - now traverse the distance array and keep count of even level and odd level
- Calculate total as ((even_count * (even_count-1)) + (odd_count * (odd_count-1))/2
Below is the implementation of above approach:
C++
// C++ program to find // the count of nodes // at even distance #include <bits/stdc++.h> using namespace std; // Dfs function to find count of nodes at // even distance void dfs(vector< int > graph[], int node, int dist[], bool vis[], int c) { if (vis[node]) { return ; } // Set flag as true for current // node in visited array vis[node] = true ; // Insert the distance in // dist array for current // visited node u dist[node] = c; for ( int i = 0; i < graph[node].size(); i++) { // If its neighbours are not vis, // run dfs for them if (!vis[graph[node][i]]) { dfs(graph, graph[node][i], dist, vis, c + 1); } } } int countOfNodes(vector< int > graph[], int n) { // bool array to // mark visited nodes bool vis[n + 1] = { false }; // Integer array to // compute distance int dist[n + 1] = { 0 }; dfs(graph, 1, dist, vis, 0); int even = 0, odd = 0; // Traverse the distance array // and count the even and odd levels for ( int i = 1; i <= n; i++) { if (dist[i] % 2 == 0) { even++; } else { odd++; } } int ans = ((even * (even - 1)) + (odd * (odd - 1))) / 2; return ans; } // Driver code int main() { int n = 5; vector< int > graph[n + 1] = { {}, { 2 }, { 1, 3 }, { 2 } }; int ans = countOfNodes(graph, n); cout << ans << endl; return 0; } |
Java
// Java program to find the count of // nodes at even distance import java.util.*; class GFG { // Dfs function to find count of nodes at // even distance static void dfs(Vector<Integer> graph[], int node, int dist[], boolean vis[], int c) { if (vis[node]) { return ; } // Set flag as true for current // node in visited array vis[node] = true ; // Insert the distance in // dist array for current // visited node u dist[node] = c; for ( int i = 0 ; i < graph[node].size(); i++) { // If its neighbours are not vis, // run dfs for them if (!vis[graph[node].get(i)]) { dfs(graph, graph[node].get(i), dist, vis, c + 1 ); } } } static int countOfNodes(Vector<Integer> graph[], int n) { // bool array to // mark visited nodes boolean []vis = new boolean [n + 1 ]; // Integer array to // compute distance int []dist = new int [n + 1 ]; dfs(graph, 1 , dist, vis, 0 ); int even = 0 , odd = 0 ; // Traverse the distance array // and count the even and odd levels for ( int i = 1 ; i <= n; i++) { if (dist[i] % 2 == 0 ) { even++; } else { odd++; } } int ans = ((even * (even - 1 )) + (odd * (odd - 1 ))) / 2 ; return ans; } // Driver code public static void main(String[] args) { int n = 5 ; Vector<Integer> []graph = new Vector[n + 1 ]; for ( int i = 0 ; i< n + 1 ; i++) { graph[i] = new Vector<Integer>(); } graph[ 0 ] = new Vector<Integer>(); graph[ 1 ] = new Vector(Arrays.asList( 2 )); graph[ 2 ] = new Vector<Integer>( 1 , 3 ); graph[ 3 ] = new Vector<Integer>( 2 ); int ans = countOfNodes(graph, n); System.out.println(ans); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find # the count of nodes # at even distance # Dfs function to find count of # nodes at even distance def dfs(graph, node, dist, vis, c) : if (vis[node]) : return ; # Set flag as true for current # node in visited array vis[node] = True ; # Insert the distance in # dist array for current # visited node u dist[node] = c; for i in range ( len (graph[node])) : # If its neighbours are not vis, # run dfs for them if ( not vis[graph[node][i]]) : dfs(graph, graph[node][i], dist, vis, c + 1 ); def countOfNodes(graph, n) : # bool array to # mark visited nodes vis = [ False ] * (n + 1 ); # Integer array to # compute distance dist = [ 0 ] * (n + 1 ); dfs(graph, 1 , dist, vis, 0 ); even = 0 ; odd = 0 ; # Traverse the distance array # and count the even and odd levels for i in range ( 1 , n + 1 ) : if (dist[i] % 2 = = 0 ) : even + = 1 ; else : odd + = 1 ; ans = ((even * (even - 1 )) + (odd * (odd - 1 ))) / / 2 ; return ans; # Driver code if __name__ = = "__main__" : n = 5 ; graph = [[], [ 2 ], [ 1 , 3 ], [ 2 ]]; ans = countOfNodes(graph, n); print (ans); # This code is contributed by kanugargng |
C#
// C# program to find the count of // nodes at even distance using System; using System.Collections.Generic; class GFG { // Dfs function to find count of // nodes at even distance static void dfs(List< int > []graph, int node, int []dist, bool []vis, int c) { if (vis[node]) { return ; } // Set flag as true for current // node in visited array vis[node] = true ; // Insert the distance in // dist array for current // visited node u dist[node] = c; for ( int i = 0; i < graph[node].Count; i++) { // If its neighbours are not vis, // run dfs for them if (!vis[graph[node][i]]) { dfs(graph, graph[node][i], dist, vis, c + 1); } } } static int countOfNodes(List< int > []graph, int n) { // bool array to // mark visited nodes bool []vis = new bool [n + 1]; // int array to // compute distance int []dist = new int [n + 1]; dfs(graph, 1, dist, vis, 0); int even = 0, odd = 0; // Traverse the distance array // and count the even and odd levels for ( int i = 1; i <= n; i++) { if (dist[i] % 2 == 0) { even++; } else { odd++; } } int ans = ((even * (even - 1)) + (odd * (odd - 1))) / 2; return ans; } // Driver code public static void Main(String[] args) { int n = 5; List< int > []graph = new List< int >[n + 1]; for ( int i = 0; i< n + 1; i++) { graph[i] = new List< int >(); } graph[0] = new List< int >{}; graph[1] = new List< int >{2}; graph[2] = new List< int >{1, 3}; graph[3] = new List< int >{2}; int ans = countOfNodes(graph, n); Console.WriteLine(ans); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to find the count of // nodes at even distance // Dfs function to find count of // nodes at even distance function dfs(graph, node, dist, vis, c) { if (vis[node]) { return ; } // Set flag as true for current // node in visited array vis[node] = true ; // Insert the distance in // dist array for current // visited node u dist[node] = c; for ( var i = 0; i < graph[node].length; i++) { // If its neighbours are not vis, // run dfs for them if (!vis[graph[node][i]]) { dfs(graph, graph[node][i], dist, vis, c + 1); } } } function countOfNodes(graph, n) { // bool array to // mark visited nodes var vis = Array(n+1).fill( false ); // int array to // compute distance var dist = Array(n+1).fill(0); dfs(graph, 1, dist, vis, 0); var even = 0, odd = 0; // Traverse the distance array // and count the even and odd levels for ( var i = 1; i <= n; i++) { if (dist[i] % 2 == 0) { even++; } else { odd++; } } var ans = ((even * (even - 1)) + (odd * (odd - 1))) / 2; return ans; } // Driver code var n = 5; var graph = Array.from(Array(n+1), ()=>Array()); graph[1] = [2]; graph[2] = [1, 3]; graph[3] = [2]; var ans = countOfNodes(graph, n); document.write(ans); </script> |
Output:
6
Time Complexity: O(V+E)
Contact Us