Horje
Find the path from root to a vertex such that all K vertices belongs to this path or 1 distance away

Given a tree consisting of N vertices numbered from 1 to N rooted at vertex 1. You are given Q queries. Each query consists of the set of K distinct vertices vi[1], vi[2],…, vi[K]. The task is to determine if there is a path from the root to some vertex X such that each of the given K vertices either belongs to this path or has the distance 1 to some vertex of this path.

Example:

Input: N= 10, Q= 6, edges = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, {7, 8}, {7, 9}, {9, 10}}, queries = {{3, 8, 9, 10}, {2, 4, 6}, {2, 1, 5}, {4, 8, 2}, {6, 10}, {5, 4, 7}}
Output:
YES
YES
YES
YES
NO
NO

Input: N= 2, Q= 3, edges = {{1, 2}}, queries = {{1, 1}, {1, 2}, {2, 1, 2}}
Output:
YES
YES
YES

Approach: The problem can be solved using the following approach:

The idea is to use Depth-First Search (DFS) to traverse the tree and record entry and exit times for each node. For each query, check if there is a path from the root to some vertex that includes all the parent nodes of the vertices in the query. This is done by comparing the maximum entry time and the minimum exit time among the parent nodes of the vertices in the query. If the minimum exit time is greater than the maximum entry time, it means such a path exists.

Steps-by-step approach:

  • Perform DFS: Traverse the tree using Depth-First Search (DFS) starting from the root node. Record the entry and exit times for each node during this traversal.
  • Record Parent Nodes: While performing DFS, also keep track of the parent of each node.
  • Process Queries: For each query, do the following:
    • Find Max Entry and Min Exit Times: Determine the maximum entry time and the minimum exit time among the parent nodes of the vertices in the query.
    • Check Path Existence: If the minimum exit time is greater than the maximum entry time, it means there exists a path from the root to some vertex that includes all the parent nodes of the vertices in the query. In this case, output “YES”. Otherwise, output “NO”.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
const int MAX_NODES = 2E5 + 5;
 
// Declare adjacency list for the graph
vector<int> adjacencyList[MAX_NODES];
 
// Declare arrays for DFS traversal timestamps and parent
// nodes
int entryTime[MAX_NODES], exitTime[MAX_NODES],
    parent[MAX_NODES];
 
// Time counter for DFS traversal
int timeCounter = 0;
 
// DFS function to populate entryTime, exitTime, and parent
// arrays
void depthFirstSearch(int currentNode, int parentNode)
{
    entryTime[currentNode] = timeCounter++;
    parent[currentNode] = parentNode;
    for (auto adjacentNode : adjacencyList[currentNode]) {
        if (adjacentNode != parentNode)
            depthFirstSearch(adjacentNode, currentNode);
    }
    exitTime[currentNode] = timeCounter++;
}
 
int main()
{
    // Provided input
    int numNodes = 10, numQueries = 6;
 
    // Edges of the tree
    vector<pair<int, int> > edges
        = { { 1, 2 }, { 1, 3 }, { 1, 4 },
            { 2, 5 }, { 2, 6 }, { 3, 7 },
            { 7, 8 }, { 7, 9 }, { 9, 10 } };
 
    // Queries
    vector<vector<int> > queries
        = { { 3, 8, 9, 10 }, { 2, 4, 6 }, { 2, 1, 5 },
            { 4, 8, 2 },     { 6, 10 },   { 5, 4, 7 } };
 
    // Construct the graph
    for (auto edge : edges) {
        int node1 = edge.first, node2 = edge.second;
        adjacencyList[node1].push_back(node2);
        adjacencyList[node2].push_back(node1);
    }
 
    // Perform DFS traversal from the root node
    depthFirstSearch(1, 1);
 
    // Process each query
    for (auto query : queries) {
        int numVerticesInQuery = query.size(),
            maxEntryTime = -1, minExitTime = 1e9;
        for (int vertex : query) {
            vertex = parent[vertex]; // Consider parent of
                                     // the vertex for the
                                     // path condition
            minExitTime
                = min(minExitTime, exitTime[vertex]);
            maxEntryTime
                = max(maxEntryTime, entryTime[vertex]);
        }
 
        // If the earliest exit time is later than the
        // latest entry time, it means there exists a path
        // satisfying the condition
        if (minExitTime > maxEntryTime)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
 
    return 0;
}

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class TreeQueries {
 
    static final int MAX_NODES = 200005;
 
    // Declare adjacency list for the graph
    static List<Integer>[] adjacencyList = new ArrayList[MAX_NODES];
 
    // Declare arrays for DFS traversal timestamps and parent nodes
    static int[] entryTime = new int[MAX_NODES];
    static int[] exitTime = new int[MAX_NODES];
    static int[] parent = new int[MAX_NODES];
 
    // Time counter for DFS traversal
    static int timeCounter = 0;
 
    // DFS function to populate entryTime, exitTime, and parent arrays
    static void depthFirstSearch(int currentNode, int parentNode) {
        entryTime[currentNode] = timeCounter++;
        parent[currentNode] = parentNode;
        for (int adjacentNode : adjacencyList[currentNode]) {
            if (adjacentNode != parentNode)
                depthFirstSearch(adjacentNode, currentNode);
        }
        exitTime[currentNode] = timeCounter++;
    }
 
    public static void main(String[] args) {
        // Provided input
        int numNodes = 10, numQueries = 6;
 
        // Edges of the tree
        List<int[]> edges = Arrays.asList(
                new int[]{1, 2}, new int[]{1, 3}, new int[]{1, 4},
                new int[]{2, 5}, new int[]{2, 6}, new int[]{3, 7},
                new int[]{7, 8}, new int[]{7, 9}, new int[]{9, 10}
        );
 
        // Queries
        List<List<Integer>> queries = Arrays.asList(
                Arrays.asList(3, 8, 9, 10), Arrays.asList(2, 4, 6),
                Arrays.asList(2, 1, 5), Arrays.asList(4, 8, 2),
                Arrays.asList(6, 10), Arrays.asList(5, 4, 7)
        );
 
        // Initialize adjacency list
        for (int i = 1; i <= numNodes; i++) {
            adjacencyList[i] = new ArrayList<>();
        }
 
        // Construct the graph
        for (int[] edge : edges) {
            int node1 = edge[0], node2 = edge[1];
            adjacencyList[node1].add(node2);
            adjacencyList[node2].add(node1);
        }
 
        // Perform DFS traversal from the root node
        depthFirstSearch(1, 1);
 
        // Process each query
        for (List<Integer> query : queries) {
            int numVerticesInQuery = query.size(),
                    maxEntryTime = -1, minExitTime = (int) 1e9;
            for (int vertex : query) {
                vertex = parent[vertex]; // Consider parent of the vertex for the path condition
                minExitTime = Math.min(minExitTime, exitTime[vertex]);
                maxEntryTime = Math.max(maxEntryTime, entryTime[vertex]);
            }
 
            // If the earliest exit time is later than the latest entry time,
            // it means there exists a path satisfying the condition
            if (minExitTime > maxEntryTime)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}
 
// This code is contributed by akshitaguprzj3

Python3

MAX_NODES = 2 * 10**5 + 5
 
# Declare adjacency list for the graph
adjacencyList = [[] for _ in range(MAX_NODES)]
 
# Declare arrays for DFS traversal timestamps and parent nodes
entryTime = [0] * MAX_NODES
exitTime = [0] * MAX_NODES
parent = [0] * MAX_NODES
 
# Time counter for DFS traversal
timeCounter = 0
 
# DFS function to populate entryTime, exitTime, and parent arrays
def depthFirstSearch(currentNode, parentNode):
    global timeCounter
    entryTime[currentNode] = timeCounter
    timeCounter += 1
    parent[currentNode] = parentNode
    for adjacentNode in adjacencyList[currentNode]:
        if adjacentNode != parentNode:
            depthFirstSearch(adjacentNode, currentNode)
    exitTime[currentNode] = timeCounter
    timeCounter += 1
 
numNodes = 10
numQueries = 6
 
# Edges of the tree
edges = [(1, 2), (1, 3), (1, 4), (2, 5), (2, 6), (3, 7), (7, 8), (7, 9), (9, 10)]
 
# Queries
queries = [
    [3, 8, 9, 10],
    [2, 4, 6],
    [2, 1, 5],
    [4, 8, 2],
    [6, 10],
    [5, 4, 7]
]
 
# Construct the graph
for edge in edges:
    node1, node2 = edge
    adjacencyList[node1].append(node2)
    adjacencyList[node2].append(node1)
 
# Perform DFS traversal from the root node
depthFirstSearch(1, 1)
 
# Process each query
for query in queries:
    numVerticesInQuery = len(query)
    maxEntryTime = -1
    minExitTime = 10**9
    for vertex in query:
        vertex = parent[vertex]  # Consider parent of the vertex for the path condition
        minExitTime = min(minExitTime, exitTime[vertex])
        maxEntryTime = max(maxEntryTime, entryTime[vertex])
 
    # If the earliest exit time is later than the latest entry time, it means there exists a path
    # satisfying the condition
    if minExitTime > maxEntryTime:
        print("YES")
    else:
        print("NO")

C#

using System;
using System.Collections.Generic;
 
class GFG
{
    const int MAX_NODES = 200005;
 
    // Declare adjacency list for the graph
    static List<int>[] adjacencyList = new List<int>[MAX_NODES];
 
    // Declare arrays for DFS traversal timestamps and parent nodes
    static int[] entryTime = new int[MAX_NODES];
    static int[] exitTime = new int[MAX_NODES];
    static int[] parent = new int[MAX_NODES];
 
    // Time counter for DFS traversal
    static int timeCounter = 0;
 
    // DFS function to populate entryTime, exitTime, and parent arrays
    static void DepthFirstSearch(int currentNode, int parentNode)
    {
        entryTime[currentNode] = timeCounter++;
        parent[currentNode] = parentNode;
        foreach (var adjacentNode in adjacencyList[currentNode])
        {
            if (adjacentNode != parentNode)
                DepthFirstSearch(adjacentNode, currentNode);
        }
        exitTime[currentNode] = timeCounter++;
    }
 
    static void Main(string[] args)
    {
        // Provided input
        //int numNodes = 10, numQueries = 6;
 
        // Initialize adjacency list
        for (int i = 0; i < MAX_NODES; i++)
        {
            adjacencyList[i] = new List<int>();
        }
 
        // Edges of the tree
        List<Tuple<int, int>> edges = new List<Tuple<int, int>> {
            Tuple.Create(1, 2), Tuple.Create(1, 3), Tuple.Create(1, 4),
            Tuple.Create(2, 5), Tuple.Create(2, 6), Tuple.Create(3, 7),
            Tuple.Create(7, 8), Tuple.Create(7, 9), Tuple.Create(9, 10)
        };
 
        // Queries
        List<List<int>> queries = new List<List<int>> {
            new List<int>{ 3, 8, 9, 10 }, new List<int>{ 2, 4, 6 },
            new List<int>{ 2, 1, 5 }, new List<int>{ 4, 8, 2 },
            new List<int>{ 6, 10 }, new List<int>{ 5, 4, 7 }
        };
 
        // Construct the graph
        foreach (var edge in edges)
        {
            int node1 = edge.Item1, node2 = edge.Item2;
            adjacencyList[node1].Add(node2);
            adjacencyList[node2].Add(node1);
        }
 
        // Perform DFS traversal from the root node
        DepthFirstSearch(1, 1);
 
        // Process each query
        foreach (var query in queries)
        {
            int numVerticesInQuery = query.Count;
            int maxEntryTime = -1, minExitTime = 1000000000;
            foreach (int vertex in query)
            {
                int parentVertex = parent[vertex]; // Consider parent of the vertex for
                                                   // the path condition
                minExitTime = Math.Min(minExitTime, exitTime[parentVertex]);
                maxEntryTime = Math.Max(maxEntryTime, entryTime[parentVertex]);
            }
 
            // If the earliest exit time is later than the latest entry time,
            // it means there exists a path satisfying the condition
            if (minExitTime > maxEntryTime)
                Console.WriteLine("YES");
            else
                Console.WriteLine("NO");
        }
    }
}

Javascript

const MAX_NODES = 200005;
 
// Initialize adjacency list
const adjacencyList = new Array(MAX_NODES).fill(null).map(() => []);
 
// Declare arrays for DFS traversal timestamps and parent nodes
const entryTime = new Array(MAX_NODES).fill(0);
const exitTime = new Array(MAX_NODES).fill(0);
const parent = new Array(MAX_NODES).fill(0);
 
// Time counter for DFS traversal
let timeCounter = 0;
 
// DFS function to populate entryTime, exitTime, and parent arrays
function depthFirstSearch(currentNode, parentNode) {
    entryTime[currentNode] = timeCounter++;
    parent[currentNode] = parentNode;
    for (const adjacentNode of adjacencyList[currentNode]) {
        if (adjacentNode !== parentNode)
            depthFirstSearch(adjacentNode, currentNode);
    }
    exitTime[currentNode] = timeCounter++;
}
 
// Provided input
const edges = [
    [1, 2], [1, 3], [1, 4],
    [2, 5], [2, 6], [3, 7],
    [7, 8], [7, 9], [9, 10]
];
 
const queries = [
    [3, 8, 9, 10], [2, 4, 6],
    [2, 1, 5], [4, 8, 2],
    [6, 10], [5, 4, 7]
];
 
// Construct the graph
for (const edge of edges) {
    const [node1, node2] = edge;
    adjacencyList[node1].push(node2);
    adjacencyList[node2].push(node1);
}
 
// Perform DFS traversal from the root node
depthFirstSearch(1, 1);
 
// Process each query
for (const query of queries) {
    let maxEntryTime = -1;
    let minExitTime = 1000000000;
    for (const vertex of query) {
        const parentVertex = parent[vertex];
        minExitTime = Math.min(minExitTime, exitTime[parentVertex]);
        maxEntryTime = Math.max(maxEntryTime, entryTime[parentVertex]);
    }
 
    // If the earliest exit time is later than the latest entry time,
    // it means there exists a path satisfying the condition
    if (minExitTime > maxEntryTime)
        console.log("YES");
    else
        console.log("NO");
}

Output

YES
YES
YES
YES
NO
NO

Time complexity: O(n + q), where n is the number of nodes in the tree and q is the number of queries. This is because the solution performs a DFS traversal on the tree once (which takes O(n) time), and then processes each query in constant time (which takes O(q) time).

Auxiliary space: O(n), where n is the number of nodes in the tree. This is because the solution uses an adjacency list to represent the tree and arrays to store the DFS timestamps and parent nodes for each vertex, all of which require O(n) space


 


Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Find Edge Weights in a Spanning Tree with Edge (u, v) Find Edge Weights in a Spanning Tree with Edge (u, v)
Find the Longest Non-Prefix-Suffix Substring in the Given String Find the Longest Non-Prefix-Suffix Substring in the Given String
Minimizing and Maximizing longest Increasing Subsequence (LIS) Minimizing and Maximizing longest Increasing Subsequence (LIS)
Sum and Update Queries on 3D Matrix in log(N) time Sum and Update Queries on 3D Matrix in log(N) time
Connecting Nodes in a Graph with Sum-based Edge Conditions Connecting Nodes in a Graph with Sum-based Edge Conditions

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 14



 

Horje