Encuentre el conteo de pares de Nodes a la misma distancia | Conjunto 2 (usando BFS)

N N-1 bordes

Ejemplos:

Entrada: N = 3, gráfica = {{}, {2}, {1, 3}, {2}}
Salida: 1
Explicación: Aquí hay tres pares {1, 2}, {1, 3}
y {2 , 3} y solo {1, 3} tiene una distancia uniforme entre ellos.
es decir, 1
            /
         2
      /
   3

Entrada: N = 5, gráfica = {{}, {2, 4}, {1, 3}, {2}, {1, 5}, {4}} Salida: 4 Explicación: Hay cuatro
pares {
1 , 3}, {1, 5}, {2, 4}
y {3, 5} que tiene una distancia par.

Enfoque: El enfoque DFS de este artículo ya se analiza en el Conjunto 1 de este artículo. Aquí usaremos BFS Traversal Of Graph para resolver el problema basado en la siguiente idea:

Comience a atravesar desde cualquier Node (digamos 1) como la raíz del gráfico y almacene el número de Nodes en niveles pares e impares. Los Nodes en el nivel de números pares están separados por distancias entre sí. Lo mismo es cierto para los Nodes en niveles impares.

Siga los pasos mencionados a continuación para implementar la idea:

• Cree una array para realizar un seguimiento de todos los Nodes visitados.
• Usando la cola, haga un recorrido BFS del gráfico.
• Empuje inicialmente el primer Node en la cola y luego atraviese y empuje a sus vecinos que aún no han sido visitados en la cola y continúe el BFS de esta manera.
• Cuente el número de Nodes en niveles pares (digamos X ) y niveles impares (digamos Y ).
• La respuesta será la suma del número de formas de elegir dos elementos cualesquiera de X (es decir, (X * (X – 1)) / 2) y dos elementos cualesquiera de Y (es decir, (Y * (Y – 1)) / 2 ).

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of nodes at
// even distance using BFS method
int countOfNodes(vector<int> graph[], int n)
{
    // Declare one vector to check that
    // element is visited or not
    vector<int> vis(n + 1);
 
    // Declare one queue
    queue<pair<int, int> > q;
    long long _0 = 0, _1 = 0;
 
    // Initially push the first node with its
    // level as even in the queue
    q.push({ 1, 0 });
 
    // Run this loop until q is not empty
    while (!q.empty()) {
        vis[q.front().first] = 1;
 
        // Check for the adjacent nodes
        for (auto child : graph[q.front().first]) {
            // Check only if adjacent node
            // is not visited
            if (!vis[child])
                q.push({ child, 1 - q.front().second });
        }
        if (q.front().second)
            _1++;
        else
            _0++;
        q.pop();
    }
 
    // Answer will be the sum of the number
    // of ways to choose any two elements
    // of even and odd type
    int ans
        = (_0 * (_0 - 1)) / 2
          + (_1 * (_1 - 1)) / 2;
    return ans;
}
 
// Driver code
int main()
{
    int N = 3;
 
    // Creating adjacency list for the graph
    vector<int> graph[N + 1];
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[3].push_back(2);
 
    // Function call
    cout << countOfNodes(graph, N);
    return 0;
}

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
// User defined Pair class
class Pair {
  int x;
  int y;
 
  // Constructor
  public Pair(int x, int y)
  {
    this.x = x;
    this.y = y;
  }
}
 
class GFG {
 
  static void addEdge(ArrayList<ArrayList<Integer> > adj,
                      int u, int v)
  {
    adj.get(u).add(v);
  }
 
  // Function to find the count of nodes at
  // even distance using BFS method
  public static long
    countOfNodes(ArrayList<ArrayList<Integer> > graph,
                 int n)
  {
    // Declare one vector to check that
    // element is visited or not
    int vis[] = new int[n + 1];
 
    // Declare one queue
 
    Queue<Pair> q = new LinkedList<>();
 
    long _0 = 0, _1 = 0;
 
    // Initially push the first node with its
    // level as even in the queue
    q.add(new Pair(1, 0));
 
    // Run this loop until q is not empty
    while (!q.isEmpty()) {
      vis[q.peek().x] = 1;
 
      // Check for the adjacent nodes
      for (Integer child : graph.get(q.peek().x)) {
        // Check only if adjacent node
        // is not visited
        if (vis[child] == 0)
          q.add(new Pair(child, 1 - q.peek().y));
      }
      if (q.peek().y != 0)
        _1++;
      else
        _0++;
      q.poll();
    }
 
    // Answer will be the sum of the number
    // of ways to choose any two elements
    // of even and odd type
    long ans
      = (_0 * (_0 - 1)) / 2 + (_1 * (_1 - 1)) / 2;
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 3;
 
    // Creating adjacency list for the graph
    ArrayList<ArrayList<Integer> > graph
      = new ArrayList<ArrayList<Integer> >(N + 1);
 
    for (int i = 0; i < N + 1; i++)
      graph.add(new ArrayList<Integer>());
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 1);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 2);
 
    // Function call
    System.out.print(countOfNodes(graph, N));
  }
}
 
// This code is contributed by Rohit Pradhan

# Python3 code to implement the above approach
 
# Function to find the count of nodes at
# even distance using BFS method
def countOfNodes(graph, n):
 
    # Declare one vector to check that
    # element is visited or not
    vis = [None] * (n + 1)
 
    # Declare one queue
    q = []
    _0 = 0
    _1 = 0
 
    # Initially push the first node with its
    # level as even in the queue
    q.append([1, 0])
 
    # Run this loop until q is not empty
    while (len(q) > 0):
        front = q.pop(0)
        vis[front[0]] = 1
 
        # Check for the adjacent nodes
        for child in graph[front[0]]:
            # Check only if adjacent node
            # is not visited
            if vis[child] is None:
                q.append([child, 1 - front[1]])
 
        if (front[1]):
            _1 += 1
        else:
            _0 += 1
 
    # Answer will be the sum of the number
    # of ways to choose any two elements
    # of even and odd type
    ans = (_0 * (_0 - 1)) // 2 + (_1 * (_1 - 1)) // 2
    return ans
 
# Driver code
N = 3
 
# Creating adjacency list for the graph
graph = [[]]
graph.append([2])
graph.append([1, 3])
graph.append([2])
 
# Function call
print(countOfNodes(graph, N))
 
# This code is contributed by phasing17

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
// User defined Pair class
class Pair {
  public int x;
  public int y;
 
  // Constructor
  public Pair(int x, int y)
  {
    this.x = x;
    this.y = y;
  }
}
 
class GFG {
 
  static void addEdge(List<List<int> > adj, int u, int v)
  {
    adj[u].Add(v);
  }
 
  // Function to find the count of nodes at
  // even distance using BFS method
  public static long countOfNodes(List<List<int> > graph,
                                  int n)
  {
    // Declare one vector to check that
    // element is visited or not
    int[] vis = new int[n + 1];
 
    // Declare one queue
 
    Queue<Pair> q = new Queue<Pair>();
 
    long _0 = 0, _1 = 0;
 
    // Initially push the first node with its
    // level as even in the queue
    q.Enqueue(new Pair(1, 0));
 
    // Run this loop until q is not empty
    while (q.Count > 0) {
      vis[q.Peek().x] = 1;
 
      // Check for the adjacent nodes
      foreach(int child in graph[q.Peek().x])
      {
        // Check only if adjacent node
        // is not visited
        if (vis[child] == 0)
          q.Enqueue(
          new Pair(child, 1 - q.Peek().y));
      }
      if (q.Peek().y != 0)
        _1++;
      else
        _0++;
      q.Dequeue();
    }
 
    // Answer will be the sum of the number
    // of ways to choose any two elements
    // of even and odd type
    long ans
      = (_0 * (_0 - 1)) / 2 + (_1 * (_1 - 1)) / 2;
    return ans;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    int N = 3;
 
    // Creating adjacency list for the graph
    List<List<int> > graph
      = new List<List<int> >(N + 1);
 
    for (int i = 0; i < N + 1; i++)
      graph.Add(new List<int>());
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 1);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 2);
 
    // Function call
    Console.Write(countOfNodes(graph, N));
  }
}
 
// This code is contributed by phasing17

<script>
 
// JavaScript code to implement the above approach
 
// Function to find the count of nodes at
// even distance using BFS method
function countOfNodes(graph, n)
{
 
    // Declare one vector to check that
    // element is visited or not
    let vis = new Array(n + 1);
 
    // Declare one queue
    let q = [];
    let _0 = 0, _1 = 0;
 
    // Initially push the first node with its
    // level as even in the queue
    q.push([1, 0 ]);
 
    // Run this loop until q is not empty
    while (q.length>0) {
        let front = q.shift();
        vis[front[0]] = 1;
 
        // Check for the adjacent nodes
        for (let child of graph[front[0]]) {
            // Check only if adjacent node
            // is not visited
            if (!vis[child])
                q.push([ child, 1 - front[1] ]);
        }
        if (front[1])
            _1++;
        else
            _0++;
    }
 
    // Answer will be the sum of the number
    // of ways to choose any two elements
    // of even and odd type
    let ans
        = (_0 * (_0 - 1)) / 2
        + (_1 * (_1 - 1)) / 2;
    return ans;
}
 
// Driver code
let N = 3;
 
// Creating adjacency list for the graph
let graph = new Array(N + 1).fill([]).map(()=>new Array());
graph[1].push(2);
graph[2].push(1);
graph[2].push(3);
graph[3].push(2);
 
// Function call
document.write(countOfNodes(graph, N));
 
// This code is contributed by shinjanpatra
 
</script>

1

Complejidad temporal: O(V+E) = O(N). Como V = número de Nodes = N, E = número de aristas = N-1 como se indica.
Espacio Auxiliar: O(N)