Dado un gráfico acíclico conectado con N Nodes y N-1 aristas , encuentre el par de Nodes que están a la misma distancia entre sí.
Ejemplos:
Input:
3
1 2
2 3
Output: 1
Explanation:
1
/
2
/
3
Input:
5
1 2
2 3
1 4
4 5
Output: 4
Acercarse:
- Supongamos que un gráfico tiene 6 niveles (0 a 5) los niveles 0, 2, 4 están a la misma distancia, pero los niveles 1, 3, 5 también están a la misma distancia, ya que su diferencia es 2, que es par, por lo que debemos ocuparnos de ambos. las condiciones, es decir, cuentan ambos niveles, pares e impares.
- El problema dado se puede resolver realizando dfs traversal
- Elija cualquier Node de origen como raíz y realice un recorrido de dfs y mantenga la
array visitada para realizar dfs y dist array para calcular la distancia desde la raíz - ahora recorra la array de distancia y lleve la cuenta del nivel par y el nivel impar
- Calcular el total como ((even_count * (even_count-1)) + (odd_count * (odd_count-1))/2
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
6
Complejidad temporal: O(V+E)