Encuentre un Node tal que todas las rutas desde ese Node hasta los Nodes hoja sean del mismo color

Dada una array 2D edge [][] de tipo { X, Y } que representa que hay una arista entre los Nodes X e Y en un árbol, y una array color[] que representa el valor del color del i -ésimo Node, la tarea es encontrar un Node raíz del árbol de modo que todos los Nodes secundarios del Node raíz en la misma ruta tengan el mismo valor del color. Si existen varias soluciones, imprima cualquiera de ellas. De lo contrario, imprima -1 .

Ejemplos:

Aporte: 
 

Salida:
Explicación: 
 

Todos los Nodes secundarios en la ruta desde el Node raíz (= 2) hasta el Node hoja (= 1) tienen el mismo valor del color (= 1). 
Todos los Nodes secundarios en la ruta desde el Node raíz (= 2) hasta el Node hoja (= 4) tienen el mismo valor del color (= 1). 
Por lo tanto, la salida requerida es 2.

Aporte: 
 

Salida:
Explicación: 
 

Todos los Nodes secundarios en la ruta desde el Node raíz (= 2) hasta el Node hoja (= 9) tienen el mismo valor de color (= 4). 
Todos los Nodes secundarios en la ruta desde el Node raíz (= 2) hasta el Node hoja (= 1) tienen el mismo valor de color (= 1). 
Todos los Nodes secundarios en la ruta desde el Node raíz (= 2) hasta el Node hoja (= 5) tienen el mismo valor de color (= 2). 
Todos los Nodes secundarios en la ruta desde el Node raíz (= 2) hasta el Node hoja (= 6) tienen el mismo valor del color (= 3).

Enfoque: La idea es iterar sobre todos los Nodes posibles del árbol. Para cada i -ésimo Node, verifique si cumple con la condición del Node raíz o si no usa DFS . Si se encuentra que es cierto, imprima el Node. De lo contrario, imprima -1 . Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos root , para almacenar el Node raíz del árbol que satisface la condición.
  • Iterar sobre todos los Nodes posibles del árbol. Considere cada i -ésimo Node del árbol como Node raíz y verifique si todos los Nodes secundarios en la ruta desde el Node raíz hasta el Node hoja tienen el mismo color o no usan DFS . Si se encuentra que es cierto, imprima el Node.
  • De lo contrario, imprima -1 .

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

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to perform dfs on the tree
bool dfs(int node, int c, vector<int> adj[],
         int color[], int visited[])
{
 
    // Mark visited node as true
    visited[node] = true;
 
    // If color does not match with
    // previous node on the same path
    if (color[node] != c) {
        return false;
    }
 
    // Check if current subtree
    // has all same colored nodes
    int f = 1;
 
    // Traverse all unvisited neighbors
    // node of the tree
    for (int j = 0; j < adj[node].size(); j++) {
 
        // Stores neighbors node
        // of the tree
        int neighbor = adj[node][j];
 
        // If current node is not
        // already visited
        if (!visited[neighbor]) {
 
            if (dfs(neighbor, c, adj,
                    color, visited)
                == false) {
 
                // Update f
                f = 0;
                break;
            }
        }
    }
    return f;
}
 
// Function to find the root node of
// the tree such that all child nodes
// on the same path have the same color
void findNode(int edges[][2],
              int color[], int n)
{
 
    // Store the adjacency list
    vector<int> adj[n + 1];
 
    // Traverse all edges and form
    // the adjacency list
    for (int i = 0; i < n - 1; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    // Store the root node such that all
    // child nodes on the same path have
    // the same color
    int ans = -1;
 
    // Iterate over all possible
    // nodes of the tree
    for (int i = 1; i <= n; i++) {
 
        // Check if node i satisfies
        // the condition of root node
        int f = 1;
 
        // Check if a node has been
        // visited or not
        int visited[n + 1] = { false };
 
        // Mark visited[i] as true
        visited[i] = true;
 
        // Traverse all the neighbors
        // of node i
        for (int j = 0; j < adj[i].size(); j++) {
 
            // Stores the current neighbor
            int neighbor = adj[i][j];
 
            // Perform DFS for current neighbor
            if (dfs(neighbor, color[neighbor],
                    adj, color, visited)
                == false) {
 
                // Update f
                f = 0;
                break;
            }
        }
 
        if (f == 1) {
            ans = i;
            break;
        }
    }
 
    // Print the answer
    cout << ans;
}
 
// Driver Code
int main()
{
 
    int n = 9;
    int color[n + 1] = { -1, 1, 1, 2, 2,
                         2, 3, 3, 4, 4 };
 
    int edges[][2] = { { 1, 2 }, { 2, 3 },
                       { 3, 4 }, { 4, 5 },
                       { 2, 7 }, { 7, 6 },
                       { 2, 8 }, { 8, 9 } };
 
    findNode(edges, color, n);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
 
// Function to perform dfs on the tree
static boolean dfs(int node, int c, Vector<Integer> adj[],
         int color[], boolean visited[])
{
 
    // Mark visited node as true
    visited[node] = true;
 
    // If color does not match with
    // previous node on the same path
    if (color[node] != c)
    {
        return false;
    }
 
    // Check if current subtree
    // has all same colored nodes
    boolean f = true;
 
    // Traverse all unvisited neighbors
    // node of the tree
    for (int j = 0; j < adj[node].size(); j++)
    {
 
        // Stores neighbors node
        // of the tree
        int neighbor = adj[node].get(j);
 
        // If current node is not
        // already visited
        if (!visited[neighbor])
        {
 
            if (dfs(neighbor, c, adj,
                    color, visited) == false)
            {
 
                // Update f
                f = false;
                break;
            }
        }
    }
    return f;
}
 
// Function to find the root node of
// the tree such that all child nodes
// on the same path have the same color
static void findNode(int edges[][],
              int color[], int n)
{
 
    // Store the adjacency list
    Vector<Integer> []adj = new Vector[n + 1];
    for(int i = 0; i < n + 1; i++)
        adj[i] = new Vector<Integer>();
 
    // Traverse all edges and form
    // the adjacency list
    for (int i = 0; i < n - 1; i++)
    {
        int a = edges[i][0];
        int b = edges[i][1];
        adj[a].add(b);
        adj[b].add(a);
    }
 
    // Store the root node such that all
    // child nodes on the same path have
    // the same color
    int ans = -1;
 
    // Iterate over all possible
    // nodes of the tree
    for (int i = 1; i <= n; i++)
    {
 
        // Check if node i satisfies
        // the condition of root node
        int f = 1;
 
        // Check if a node has been
        // visited or not
        boolean []visited = new boolean[n + 1];
 
        // Mark visited[i] as true
        visited[i] = true;
 
        // Traverse all the neighbors
        // of node i
        for (int j = 0; j < adj[i].size(); j++)
        {
 
            // Stores the current neighbor
            int neighbor = adj[i].get(j);
 
            // Perform DFS for current neighbor
            if (dfs(neighbor, color[neighbor],
                    adj, color, visited) == false)
            {
 
                // Update f
                f = 0;
                break;
            }
        }
        if (f == 1)
        {
            ans = i;
            break;
        }
    }
 
    // Print the answer
    System.out.print(ans);
}
 
// Driver Code
public static void main(String[] args)
{
 
    int n = 9;
    int color[] = { -1, 1, 1, 2, 2,
                         2, 3, 3, 4, 4 };
    int edges[][] = { { 1, 2 }, { 2, 3 },
                       { 3, 4 }, { 4, 5 },
                       { 2, 7 }, { 7, 6 },
                       { 2, 8 }, { 8, 9 } };
    findNode(edges, color, n);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program to implement
# the above approach
from typing import List
 
# Function to perform dfs on the tree
def dfs(node: int, c: int, adj: List[List[int]],
        color: List[int],
        visited: List[int]) -> bool:
 
    # Mark visited node as true
    visited[node] = True
 
    # If color does not match with
    # previous node on the same path
    if (color[node] != c):
        return False
 
    # Check if current subtree
    # has all same colored nodes
    f = 1
 
    # Traverse all unvisited neighbors
    # node of the tree
    for j in range(len(adj[node])):
 
        # Stores neighbors node
        # of the tree
        neighbor = adj[node][j]
 
        # If current node is not
        # already visited
        if (not visited[neighbor]):
            if not dfs(neighbor, c, adj, color, visited):
 
                # Update f
                f = 0
                break
    return f
 
# Function to find the root node of
# the tree such that all child nodes
# on the same path have the same color
def findNode(edges: List[List[int]], color: List[int], n: int) -> None:
 
    # Store the adjacency list
    adj = [[] for _ in range(n + 1)]
 
    # Traverse all edges and form
    # the adjacency list
    for i in range(n - 1):
        a = edges[i][0]
        b = edges[i][1]
        adj[a].append(b)
        adj[b].append(a)
 
    # Store the root node such that all
    # child nodes on the same path have
    # the same color
    ans = -1
 
    # Iterate over all possible
    # nodes of the tree
    for i in range(1, n + 1):
 
        # Check if node i satisfies
        # the condition of root node
        f = 1
 
        # Check if a node has been
        # visited or not
        visited = [False for _ in range(n + 1)]
 
        # Mark visited[i] as true
        visited[i] = True
 
        # Traverse all the neighbors
        # of node i
        for j in range(len(adj[i])):
 
            # Stores the current neighbor
            neighbor = adj[i][j]
 
            # Perform DFS for current neighbor
            if not dfs(neighbor, color[neighbor],
                       adj, color, visited):
 
                # Update f
                f = 0
                break
 
        if (f == 1):
            ans = i
            break
 
    # Print the answer
    print(ans)
 
# Driver Code
if __name__ == "__main__":
 
    n = 9
    color = [-1, 1, 1, 2, 2, 2, 3, 3, 4, 4]
    edges = [[1, 2], [2, 3], [3, 4], [4, 5], [2, 7], [7, 6], [2, 8], [8, 9]]
    findNode(edges, color, n)
 
# This code is contributed by sanjeev2552

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
// Function to perform dfs on the tree
static bool dfs(int node, int c, List<int> []adj,
         int []color, bool []visited)
{
 
    // Mark visited node as true
    visited[node] = true;
 
    // If color does not match with
    // previous node on the same path
    if (color[node] != c)
    {
        return false;
    }
 
    // Check if current subtree
    // has all same colored nodes
    bool f = true;
 
    // Traverse all unvisited neighbors
    // node of the tree
    for (int j = 0; j < adj[node].Count; j++)
    {
 
        // Stores neighbors node
        // of the tree
        int neighbor = adj[node][j];
 
        // If current node is not
        // already visited
        if (!visited[neighbor])
        {
 
            if (dfs(neighbor, c, adj,
                    color, visited) == false)
            {
 
                // Update f
                f = false;
                break;
            }
        }
    }
    return f;
}
 
// Function to find the root node of
// the tree such that all child nodes
// on the same path have the same color
static void findNode(int [,]edges,
              int []color, int n)
{
 
    // Store the adjacency list
    List<int> []adj = new List<int>[n + 1];
    for(int i = 0; i < n + 1; i++)
        adj[i] = new List<int>();
 
    // Traverse all edges and form
    // the adjacency list
    for (int i = 0; i < n - 1; i++)
    {
        int a = edges[i, 0];
        int b = edges[i, 1];
        adj[a].Add(b);
        adj[b].Add(a);
    }
 
    // Store the root node such that all
    // child nodes on the same path have
    // the same color
    int ans = -1;
 
    // Iterate over all possible
    // nodes of the tree
    for (int i = 1; i <= n; i++)
    {
 
        // Check if node i satisfies
        // the condition of root node
        int f = 1;
 
        // Check if a node has been
        // visited or not
        bool []visited = new bool[n + 1];
 
        // Mark visited[i] as true
        visited[i] = true;
 
        // Traverse all the neighbors
        // of node i
        for (int j = 0; j < adj[i].Count; j++)
        {
 
            // Stores the current neighbor
            int neighbor = adj[i][j];
 
            // Perform DFS for current neighbor
            if (dfs(neighbor, color[neighbor],
                    adj, color, visited) == false)
            {
 
                // Update f
                f = 0;
                break;
            }
        }
        if (f == 1)
        {
            ans = i;
            break;
        }
    }
 
    // Print the answer
    Console.Write(ans);
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 9;
    int []color = { -1, 1, 1, 2, 2,
                         2, 3, 3, 4, 4 };
    int [,]edges = { { 1, 2 }, { 2, 3 },
                       { 3, 4 }, { 4, 5 },
                       { 2, 7 }, { 7, 6 },
                       { 2, 8 }, { 8, 9 } };
    findNode(edges, color, n);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
  // JavaScript program for the above approach
   
  // Function to perform dfs on the tree
  function dfs(node, c, adj, color, visited)
  {
    
      // Mark visited node as true
      visited[node] = true;
    
      // If color does not match with
      // previous node on the same path
      if (color[node] != c)
      {
          return false;
      }
    
      // Check if current subtree
      // has all same colored nodes
      let f = true;
    
      // Traverse all unvisited neighbors
      // node of the tree
      for (let j = 0; j < adj[node].length; j++)
      {
    
          // Stores neighbors node
          // of the tree
          let neighbor = adj[node][j];
    
          // If current node is not
          // already visited
          if (!visited[neighbor])
          {
    
              if (dfs(neighbor, c, adj, color, visited) == false)
              {
    
                  // Update f
                  f = false;
                  break;
              }
          }
      }
      return f;
  }
    
  // Function to find the root node of
  // the tree such that all child nodes
  // on the same path have the same color
  function findNode(edges, color, n)
  {
    
      // Store the adjacency list
      let adj = new Array(n + 1);
      for(let i = 0; i < n + 1; i++)
      {
          adj[i] = [];
      }
    
      // Traverse all edges and form
      // the adjacency list
      for (let i = 0; i < n - 1; i++)
      {
          let a = edges[i][0];
          let b = edges[i][1];
          adj[a].push(b);
          adj[b].push(a);
      }
    
      // Store the root node such that all
      // child nodes on the same path have
      // the same color
      let ans = -1;
    
      // Iterate over all possible
      // nodes of the tree
      for (let i = 1; i <= n; i++)
      {
    
          // Check if node i satisfies
          // the condition of root node
          let f = 1;
    
          // Check if a node has been
          // visited or not
          let visited = new Array(n + 1);
          visited.fill(false);
    
          // Mark visited[i] as true
          visited[i] = true;
    
          // Traverse all the neighbors
          // of node i
          for (let j = 0; j < adj[i].length; j++)
          {
    
              // Stores the current neighbor
              let neighbor = adj[i][j];
    
              // Perform DFS for current neighbor
              if (dfs(neighbor, color[neighbor],
                      adj, color, visited) == false)
              {
    
                  // Update f
                  f = 0;
                  break;
              }
          }
          if (f == 1)
          {
              ans = i;
              break;
          }
      }
    
      // Print the answer
      document.write(ans);
  }
   
  let n = 9;
  let color = [ -1, 1, 1, 2, 2, 2, 3, 3, 4, 4 ];
  let edges = [ [ 1, 2 ], [ 2, 3 ],
                     [ 3, 4 ], [ 4, 5 ],
                     [ 2, 7 ], [ 7, 6 ],
                     [ 2, 8 ], [ 8, 9 ] ];
  findNode(edges, color, n);
     
</script>
Producción: 

2

 

Complejidad temporal: O(N 2 )
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por utkershgahoi140 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 *