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: 2
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: 2
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