Найдите путь от корня к заданным узлам дерева для нескольких запросов

Опубликовано: 2 Декабря, 2021

Дано дерево с N вершинами, пронумерованными от 0 до N - 1 (0- ^й узел является корневым). Также, учитывая q запросов, содержащих узлы в дереве. Задача состоит в том, чтобы найти путь от корневого узла к заданному узлу для нескольких запросов.

Примеры:

 Ввод: N = 6, q [] = {2, 4}
Дерево:
                    0
                   / 
                  1 2
                  |
                  3
                 / 
                4 5
Выход:
0 2
0 1 3 4
Путь от корневого узла к узлу 2 равен 0 -> 2.
Путь от корневого узла к узлу 4: 0 -> 1 -> 3 -> 4.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: путь от любой корневой вершины к любой вершине i - это путь от корневой вершины до ее родителя, за которым следует сам родитель. Это может быть достигнуто путем изменения обхода дерева в ширину. В списке путей для каждой непосещенной вершины добавьте копию пути ее родительского элемента в список, а затем добавьте родительский элемент в список.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ implementation of the approach
 #include <bits/stdc++.h>
 using namespace std;
 const int sz = 1e5;
 // Adjacency list representation
 // of the tree
 vector< int > tree[sz];
 // Boolean array to mark all the
 // vertices which are visited
 bool vis[sz];
 // Array of vector where ith index
 // stores the path from the root
 // node to the ith node
 vector< int > path[sz];
 // Utility function to create an
 // edge between two vertices
 void addEdge( int a, int b)
 {
    // Add a to b's list
    tree[a].push_back(b);
    // Add b to a's list
    tree[b].push_back(a);
 }
 // Modified Breadth-First Function
 void bfs( int node)
 {
    // Create a queue of {child, parent}
    queue<pair< int , int > > qu; 
    // Push root node in the front of
    // the queue and mark as visited
    qu.push({ node, -1 });
    vis[node] = true ; 
    while (!qu.empty()) {
        pair< int , int > p = qu.front(); 
        // Dequeue a vertex from queue
        qu.pop();
        vis[p.first] = true ; 
        // Get all adjacent vertices of the dequeued
        // vertex s. If any adjacent has not
        // been visited then enqueue it
        for ( int child : tree[p.first]) {
            if (!vis[child]) {
                qu.push({ child, p.first });
                // Path from the root to this vertex is
                // the path from root to the parent
                // of this vertex followed by the
                // parent itself
                path[child] = path[p.first];
                path[child].push_back(p.first);
            }
        }
    }
 }
 // Utility Function to print the
 // path from root to given node
 void displayPath( int node)
 {
    vector< int > ans = path[node];
    for ( int k : ans) {
        cout << k << " " ;
    }
    cout << node << '
' ;
 }
 // Driver code
 int main()
 {
    // Number of vertices
    int n = 6; 
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(3, 4);
    addEdge(3, 5);
    // Calling modified bfs function
    bfs(0);
    // Display paths from root vertex
    // to the given vertices
    displayPath(2);
    displayPath(4);
    displayPath(5);
    return 0;
 }

Ява

 // Java implementation of the approach
 import java.util.*;
 @SuppressWarnings ( "unchecked" )
 class GFG { 
    static class Pair<T, V> {
        T first;
        V second;
        Pair() {
        }
        Pair(T first, V second) {
            this .first = first;
            this .second = second;
        }
    }
    static int sz = ( int ) 1e5; 
    // Adjacency list representation
    // of the tree
    static Vector<Integer>[] tree = new Vector[sz]; 
    // Boolean array to mark all the
    // vertices which are visited
    static boolean [] vis = new boolean [sz]; 
    // Array of vector where ith index
    // stores the path from the root
    // node to the ith node
    static Vector<Integer>[] path = new Vector[sz]; 
    // Utility function to create an
    // edge between two vertices
    static void addEdge( int a, int b) { 
        // Add a to b's list
        tree[a].add(b);
        // Add b to a's list
        tree[b].add(a);
    }
    // Modified Breadth-First Function
    static void bfs( int node) { 
        // Create a queue of {child, parent}
        Queue<Pair<Integer, Integer>> qu = new LinkedList<>(); 
        // Push root node in the front of
        // the queue and mark as visited
        qu.add( new Pair<>(node, - 1 ));
        vis[node] = true ; 
        while (!qu.isEmpty()) { 
            // Dequeue a vertex from queue
            Pair<Integer, Integer> p = qu.poll();
            vis[p.first] = true ; 
            // Get all adjacent vertices of the dequeued
            // vertex s. If any adjacent has not
            // been visited then enqueue it
            for ( int child : tree[p.first]) {
                if (!vis[child]) {
                    qu.add( new Pair<>(child, p.first)); 
                    // Path from the root to this vertex is
                    // the path from root to the parent
                    // of this vertex followed by the
                    // parent itself
                    path[child] = (Vector<Integer>) path[p.first].clone();
                    path[child].add(p.first);
                }
            }
        }
    }
    // Utility Function to print the
    // path from root to given node
    static void displayPath( int node) {
        for ( int k : path[node]) {
            System.out.print(k + " " );
        }
        System.out.println(node);
    }
    // Driver Code
    public static void main(String[] args) {
        for ( int i = 0 ; i < sz; i++) {
            tree[i] = new Vector<>();
            path[i] = new Vector<>();
            vis[i] = false ;
        }
        // Number of vertices
        int n = 6 ; 
        addEdge( 0 , 1 );
        addEdge( 0 , 2 );
        addEdge( 1 , 3 );
        addEdge( 3 , 4 );
        addEdge( 3 , 5 ); 
        // Calling modified bfs function
        bfs( 0 ); 
        // Display paths from root vertex
        // to the given vertices
        displayPath( 2 );
        displayPath( 4 );
        displayPath( 5 );
    }
 }
 // This code is contributed by
 // sanjeev2552

Python3

 # Python3 implementation of the approach
 from collections import deque as queue
 sz = 7
 # Adjacency list representation
 # of the tree
 tree = [[] for i in range (sz)]
 # Boolean array to mark all the
 # vertices which are visited
 vis = [ False ] * sz
 # Array of vector where ith index
 # stores the path from the root
 # node to the ith node
 path = [[] for i in range (sz)]
 # Utility function to create an
 # edge between two vertices
 def addEdge(a, b): 
    # Add a to b's list
    tree[a].append(b)
    # Add b to a's list
    tree[b].append(a)
 # Modified Breadth-First Function
 def bfs(node): 
    # Create a queue of {child, parent}
    qu = queue() 
    # Push root node in the front of
    # the queue and mark as visited
    qu.append([node, - 1 ])
    vis[node] = True 
    while ( len (qu) > 0 ):
        p = qu.popleft()
        
        #print(p,p[0],p[1])
        # Dequeue a vertex from queue
        # qu.pop()
        vis[p[ 0 ]] = True 
        # Get all adjacent vertices of
        # the dequeued vertex s. If any
        # adjacent has not been visited
        # then enqueue it
        for child in tree[p[ 0 ]]:
            if (vis[child] = = False ):
                qu.append([child, p[ 0 ]]) 
                # Path from the root to this
                # vertex is the path from root
                # to the parent of this vertex
                # followed by the parent itself
                for u in path[p[ 0 ]]:
                    path[child].append(u)
                path[child].append(p[ 0 ])
                
                #print(child,":",path[0])
 # Utility Function to prthe
 # path from root to given node
 def displayPath(node):
    
    ans = path[node]
    for k in ans:
        print (k, end = " " )
        
    print (node)
 # Driver code
 if __name__ = = '__main__' : 
    # Number of vertices
    n = 6 
    addEdge( 0 , 1 )
    addEdge( 0 , 2 )
    addEdge( 1 , 3 )
    addEdge( 3 , 4 )
    addEdge( 3 , 5 ) 
    # Calling modified bfs function
    bfs( 0 ) 
    # Display paths from root vertex
    # to the given vertices
    displayPath( 2 )
    displayPath( 4 )
    displayPath( 5 )
 # This code is contributed by mohit kumar 29

Выход:

 0 2
0 1 3 4
0 1 3 5

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Олимпиады по программированию Алгоритмы Структуры данных

Найдите путь от корня к заданным узлам дерева для нескольких запросов

C ++

Ява

Python3

РЕКОМЕНДУЕМЫЕ СТАТЬИ