Cuente los pares de vértices en Tree de manera que la distancia entre ellos sea par

Posted on by Rudeus Greyrat

Dado un árbol de N vértices, la tarea es encontrar el número de pares de vértices tales que la distancia entre ellos sea par pero no pueda ser 0

Ejemplos:

Entrada: N = 5, Bordes = [ [1, 0], [2, 1], [3, 1], [4, 3] ]

                        0
                     /          
                  1           
               / \ 
            2 3
                        \
                         4 

Salida: 4
Explicación : Hay cuatro pares de vértices tales que la distancia entre ellos es par.
Son [0, 2], [0, 3], [3, 2] y [1, 4].

Entrada : N = 6, Bordes: [[1, 0], [2, 1], [3, 1], [4, 2], [5, 3]]

                           0
                        /         
                     1            
               / \
           2 3
        //
     4 5
Salida : 6
Explicación : Hay 6 pares de vértices tales que la distancia entre ellos es par. Son [0, 2], [4, 1], [3, 0], [4, 5], [1, 5] y [2, 3].

 

Enfoque ingenuo: el enfoque ingenuo consiste en probar todos los pares posibles de vértices, encontrar la distancia entre ellos y verificar si la distancia es uniforme. Siga los pasos que se mencionan a continuación para resolver el problema:

  • Iterar sobre todos los vértices para i = 0 a N-1 :
    • Iterar de j = i+1 a N-1:
      • Encuentre la distancia de i a j usando DFS .
      • Si la distancia es par entonces incremente el conteo de pares.
  • Devuelve la cuenta.

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

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the distance
void dfs(int i, int par,
         vector<vector<int> >& adj,
         vector<int>& dis)
{
    // Iterate over all the edges of vertex i
    for (int j : adj[i]) {
 
        // If 'j' is not the parent of 'i'.
        if (j != par) {
 
            // Store the distance
            // from root till 'j'.
            dis[j] = dis[i] + 1;
 
            // Recurse for the child 'j'.
            dfs(j, i, adj, dis);
        }
    }
}
 
// Function to count pairs
int countPairs(int n,
               vector<vector<int> >& edges)
{
    // Stores the final answer.
    int ans = 0;
 
    // Stores the adjacency List of the tree.
    vector<vector<int> > adj(n);
 
    for (int i = 0; i < n - 1; ++i) {
 
        // Add the edge in the adjacency list.
        adj[edges[i][0]].push_back(edges[i][1]);
        adj[edges[i][1]].push_back(edges[i][0]);
    }
 
    // Stores the distance from root till 'i'.
    vector<int> dis(n);
 
    // Iterate over all 'u'
    // of the pair ('u', 'v').
    for (int i = 0; i < n; ++i) {
 
        // Set all the values
        // of 'dis[i]' to '0'.
        fill(dis.begin(), dis.end(), 0);
 
        // Do a dfs with 'i' as
        // the root of the tree.
        dfs(i, -1, adj, dis);
 
        // Iterate over the other end
        // of the pair.
        for (int j = i + 1; j < n; ++j) {
 
            // If the distance is even.
            if (dis[j] % 2 == 0) {
 
                // Increment 'ans' by 1.
                ans++;
            }
        }
    }
 
    // Return the answer 'ans'.
    return ans;
}
 
// Driver Code
int main()
{
    int N = 5;
    vector<vector<int> > edges
        = { { 1, 0 }, { 2, 1 }, { 3, 1 }, { 4, 3 } };
 
    // Function call
    cout << countPairs(N, edges);
    return 0;
}

Java

// Java code to implement above approach
import java.util.*;
 
public class Main
{
 
  // Function to find the distance
  static void dfs(int i, int par,
                  ArrayList <ArrayList<Integer> > adj,
                  ArrayList <Integer> dis)
  {
    // Iterate over all the edges of vertex i
    for (int j : adj.get(i) ) {
 
      // If 'j' is not the parent of 'i'.
      if (j != par) {
 
        // Store the distance
        // from root till 'j'.
        dis.set(j, dis.get(i) + 1);
 
        // Recurse for the child 'j'.
        dfs(j, i, adj, dis);
      }
    }
  }
 
  // Function to count pairs
  static int countPairs(int n,
                        int[][] edges)
  {
    // Stores the final answer.
    int ans = 0;
 
    // Stores the adjacency List of the tree.
    ArrayList <ArrayList<Integer> > adj =
      new ArrayList<ArrayList<Integer> >(n);
    for (int i = 0; i < n; i++)
      adj.add(new ArrayList<Integer>());
 
    for (int i = 0; i < n - 1; ++i) {
 
      // Add the edge in the adjacency list.
      adj.get(edges[i][0]).add(edges[i][1]);
      adj.get(edges[i][1]).add(edges[i][0]);
    }
 
    // Iterate over all 'u'
    // of the pair ('u', 'v').
    for (int i = 0; i < n; ++i) {
 
      ArrayList <Integer> dis =
        new ArrayList<Integer> (n);;
      // Do a dfs with 'i' as
      // the root of the tree.
      for (int j = 0; j < n; ++j) {
        dis.add(0);
      }
      dfs(i, -1, adj, dis);
 
      // Iterate over the other end
      // of the pair.
      for (int j = i + 1; j < n; ++j) {
 
        // If the distance is even.
        if (dis.get(j) % 2 == 0) {
 
          // Increment 'ans' by 1.
          ans++;
        }
      }
    }
 
    // Return the answer 'ans'.
    return ans;
  }
  // Driver Code
  public static void main(String args[])
  {
    int N = 5;
 
    // array of edges
    int[][] edges
      = { { 1, 0 }, { 2, 1 }, { 3, 1 }, { 4, 3 } };
 
    // Function call
    System.out.println( countPairs(N, edges) );
 
  }
}
 
// This code is contributed by Sachin Sahara (sachin801)

Javascript

<script>
 
// JavaScript code to implement the approach
 
// Function to find the distance
function dfs(i, par, adj, dis)
{
    // Iterate over all the edges of vertex i
    for (let j of adj[i]) {
 
        // If 'j' is not the parent of 'i'.
        if (j != par) {
 
            // Store the distance
            // from root till 'j'.
            dis[j] = dis[i] + 1;
 
            // Recurse for the child 'j'.
            dfs(j, i, adj, dis);
        }
    }
}
 
// Function to count pairs
function countPairs(n,edges)
{
    // Stores the final answer.
    let ans = 0;
 
    // Stores the adjacency List of the tree.
    let adj = new Array(n);
    for(let i=0;i<N;i++){
        adj[i] = new Array();
    }
 
    for (let i = 0; i < n - 1; ++i) {
        
        // Add the edge in the adjacency list.
        adj[edges[i][0]].push(edges[i][1]);
        adj[edges[i][1]].push(edges[i][0]);
    }
 
    // Stores the distance from root till 'i'.
    let dis = new Array(n);;
 
    // Iterate over all 'u'
    // of the pair ('u', 'v').
    for (let i = 0; i < n; ++i) {
 
        // Set all the values
        // of 'dis[i]' to '0'.
        dis.fill(0);
 
        // Do a dfs with 'i' as
        // the root of the tree.
        dfs(i, -1, adj, dis);
 
        // Iterate over the other end
        // of the pair.
        for (let j = i + 1; j < n; ++j) {
 
            // If the distance is even.
            if (dis[j] % 2 == 0) {
 
                // Increment 'ans' by 1.
                ans++;
            }
        }
    }
 
    // Return the answer 'ans'.
    return ans;
}
 
// Driver Code
 
let N = 5;
let edges = [ [ 1, 0 ], [ 2, 1 ], [ 3, 1 ], [ 4, 3 ] ];
 
// Function call
document.write(countPairs(N, edges));
 
// This code is contributed by shinjanpatra
 
</script>
Producción

4

Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(N)

Enfoque eficiente: el enfoque eficiente para resolver el problema se basa en el concepto de gráfico bipartito, como se muestra a continuación.

Todo árbol es un grafo bipartito. Entonces, todos los vértices son parte de uno de los dos conjuntos bipartitos (por ejemplo, L y R ). 
Cualquier par que tenga ambos valores de diferentes conjuntos tiene una distancia impar entre ellos y los pares con vértices del mismo conjunto tienen una distancia par entre ellos.

Con base en la observación anterior, está claro que el número total de pares son los pares posibles formados usando vértices del mismo conjunto, es decir, ( x C 2 ) + ( y C 2 ) , donde [ n C 2 = n * (n – 1)/2, x es el tamaño del conjunto L ey es el tamaño del conjunto R]. Siga los pasos que se mencionan a continuación para resolver el problema.

  • Declare e inicialice dos variables xey a 0 para almacenar el tamaño de los conjuntos bipartitos.
  • Haga que root sea parte de uno de los conjuntos bipartitos (digamos L ).
  • Inicialice una array (digamos dis[] ) para almacenar las distancias desde 0.
  • Inicie un DFS o BFS desde el vértice 0 :
    • En cada instante, iterar a través de todos los hijos, y si aún no hemos visitado a este hijo (digamos que el hijo es j ), entonces:
      • Incremente su distancia como dis[Node actual] = distancia[padre] + 1.
      • Si es par, incremente x y hágalo parte del conjunto L. De lo contrario, incremente y y hágalo parte del conjunto R.
    • Recursivamente haga lo mismo para sus hijos.
  • Finalmente, devuelve el valor de x C 2 + y C 2 .

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

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Dfs function
void dfs(int i, int par,
         vector<vector<int> >& adj,
         vector<int>& dis)
{
    // Iterate over all edges of vertex 'i'.
    for (int j : adj[i]) {
 
        // If 'j' is not the parent of 'i'.
        if (j != par) {
 
            // Store the distance
            // from root till 'j'.
            dis[j] = dis[i] + 1;
 
            // Recurse for the child 'j'.
            dfs(j, i, adj, dis);
        }
    }
}
 
// Function to count the vertices
int countPairs(int n,
               vector<vector<int> >& edges)
{
    // Stores the adjacency List of the tree.
    vector<vector<int> > adj(n);
    for (int i = 0; i < n - 1; ++i) {
 
        // Add the edge in the adjacency list.
        adj[edges[i][0]].push_back(edges[i][1]);
        adj[edges[i][1]].push_back(edges[i][0]);
    }
 
    // Stores the distance from root till 'i'.
    vector<int> dis(n);
 
    // Dfs with '0' as the root of the tree.
    dfs(0, -1, adj, dis);
 
    // To store the size of set 'L'
    // size of set 'R'.
    int x = 0, y = 0;
 
    // Iterate over all the vertices
    // of the tree.
    for (int i = 0; i < n; ++i) {
 
        // If 'i' is at an even depth.
        if (dis[i] % 2 == 0) {
 
            // Increment the size of set 'L'.
            x++;
        }
        else {
 
            // Increment the size of set 'R'.
            y++;
        }
    }
 
    // Return the answer.
    return x * (x - 1) / 2 + y * (y - 1) / 2;
}
 
// Driver Code
int main()
{
    int N = 5;
    vector<vector<int> > edges
        = { { 1, 0 }, { 2, 1 }, { 3, 1 }, { 4, 3 } };
 
    // Function call
    cout << countPairs(N, edges);
    return 0;
}

Java

// Java code to implement above approach
 
import java.util.*;
 
public class Main {
    // Function to find the distance
    static void dfs(int i, int par,
            ArrayList <ArrayList<Integer> > adj,
            ArrayList <Integer> dis)
    {
        // Iterate over all the edges of vertex i
        for (int j : adj.get(i) ) {
 
            // If 'j' is not the parent of 'i'.
            if (j != par) {
 
                // Store the distance
                // from root till 'j'.
                dis.set(j, dis.get(i) + 1);
 
                // Recurse for the child 'j'.
                dfs(j, i, adj, dis);
            }
        }
    }
 
    // Function to count pairs
    static int countPairs(int n,
                int[][] edges)
    {
        // Stores the adjacency List of the tree.
        ArrayList <ArrayList<Integer> > adj =
                        new ArrayList<ArrayList<Integer> >(n);
        for (int i = 0; i < n; i++)
            adj.add(new ArrayList<Integer>());
 
        for (int i = 0; i < n - 1; ++i) {
 
            // Add the edge in the adjacency list.
            adj.get(edges[i][0]).add(edges[i][1]);
            adj.get(edges[i][1]).add(edges[i][0]);
        }
 
        // Stores the distance from root till 'i'.
        ArrayList <Integer> dis = new ArrayList <Integer> (n);
        for (int j = 0; j < n; ++j) {
            dis.add(0);
        }
        // Dfs with '0' as the root of the tree.
        dfs(0, -1, adj, dis);
 
        // To store the size of set 'L'
        // size of set 'R'.
        int x = 0, y = 0;
 
        // Iterate over all the vertices
        // of the tree.
        for (int i = 0; i < n; ++i) {
 
            // If 'i' is at an even depth.
            if (dis.get(i) % 2 == 0) {
 
                // Increment the size of set 'L'.
                x++;
            }
            else {
 
                // Increment the size of set 'R'.
                y++;
            }
        }
 
        // Return the answer.
        return x * (x - 1) / 2 + y * (y - 1) / 2;
    }
 
    // Driver Code
    public static void main(String args[]) {
        int N = 5;
        // array of edges
        int[][] edges
            = { { 1, 0 }, { 2, 1 }, { 3, 1 }, { 4, 3 } };
 
        // Function call
        System.out.println( countPairs(N, edges) );
         
    }
}
 
// This code is contributed by Sachin Sahara (sachin801)

Python3

# python3 code to implement the approach
 
# Dfs function
def dfs(i, par, adj, dis):
 
    # Iterate over all edges of vertex 'i'.
    for j in adj[i]:
 
        # If 'j' is not the parent of 'i'.
        if (j != par):
 
            # Store the distance
            # from root till 'j'.
            dis[j] = dis[i] + 1
 
            # Recurse for the child 'j'.
            dfs(j, i, adj, dis)
 
# Function to count the vertices
def countPairs(n, edges):
 
    # Stores the adjacency List of the tree.
    adj = [[] for _ in range(n)]
    for i in range(0, n-1):
 
        # Add the edge in the adjacency list.
        adj[edges[i][0]].append(edges[i][1])
        adj[edges[i][1]].append(edges[i][0])
 
    # Stores the distance from root till 'i'.
    dis = [0 for _ in range(n)]
 
    # Dfs with '0' as the root of the tree.
    dfs(0, -1, adj, dis)
 
    # To store the size of set 'L'
    # size of set 'R'.
    x, y = 0, 0
 
    # Iterate over all the vertices
    # of the tree.
    for i in range(0, n):
 
        # If 'i' is at an even depth.
        if (dis[i] % 2 == 0):
 
            # Increment the size of set 'L'.
            x += 1
 
        else:
 
            # Increment the size of set 'R'.
            y += 1
 
    # Return the answer.
    return x * (x - 1) // 2 + y * (y - 1) // 2
 
 
# Driver Code
if __name__ == "__main__":
 
    N = 5
    edges = [[1, 0], [2, 1], [3, 1], [4, 3]]
 
    # Function call
    print(countPairs(N, edges))
 
# This code is contributed by rakeshsahni
Producción

4

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)

Publicación traducida automáticamente

Artículo escrito por rohit768 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *