ਚੈੱਕ ਕਰੋ ਕਿ ਦਰੱਖਤ ਵਿਚ ਇਕੋ ਰਸਤੇ ਤੇ ਦੋ ਨੋਡ ਹਨ ਜਾਂ ਨਹੀਂ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਤੱਥ ਫੋਰਕਾਈਟਸ ਸੈਮਸੰਗ
ਡੂੰਘਾਈ ਪਹਿਲੀ ਖੋਜ ਗਰਾਫ਼ ਗ੍ਰਾਫ ਟ੍ਰਾਵਰਸਲ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ "ਚੈੱਕ ਕਰੋ ਕਿ ਕੀ ਦਰੱਖਤ ਦੇ ਦੋ ਨੋਡ ਇਕੋ ਰਸਤੇ ਤੇ ਹਨ" ਦੱਸਦਾ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਏ n-ary ਰੁੱਖ (ਨਿਰਦੇਸ਼ਿਤ ਐਸੀਕਲਿਕ ਗ੍ਰਾਫ) ਤੇ ਜੜ੍ਹਾਂ ਹੈ ਰੂਟ ਨਾਲ ਨੋਡ ਇਕ-ਦਿਸ਼ਾਵੀ ਇਸ ਦੇ ਲੰਬਕਾਰੀ ਦੇ ਵਿਚਕਾਰ ਕਿਨਾਰੇ. ਤੁਹਾਨੂੰ ਪ੍ਰਸ਼ਨਾਂ ਦੀ ਇਕ ਸੂਚੀ ਵੀ ਦਿੱਤੀ ਗਈ ਹੈ Q.

  1. ਸੂਚੀ Q ਵਿਚਲੀ ਹਰ ਪ੍ਰਸ਼ਨ ਵਿਚ ਦੋ ਸਿਰੇ ਅਤੇ ਤੁਸੀਂ ਹੁੰਦੇ ਹਨ.
  2. ਤੁਹਾਨੂੰ ਛਾਪਣਾ ਪਏਗਾ “"ਜੇ ਨੋਡਜ਼ ਤੁਸੀਂ ਅਤੇ ਉਸੇ ਰਾਹ ਤੇ ਪਏ ਹੋ ਤੋਂ ਸ਼ੁਰੂ ਹੋਇਆ ਰੂਟ ਵਰਟੈਕਸ
  3. ਹੋਰ ਪ੍ਰਿੰਟ “ਨਹੀਂ"ਜੇ ਨੋਡਜ਼ ਤੁਸੀਂ ਵੱਖ ਵੱਖ ਮਾਰਗਾਂ ਤੇ ਖੜੇ ਹੋ ਤੋਂ ਸ਼ੁਰੂ ਹੋਇਆ ਰੂਟ ਵਰਟੈਕਸ

ਉਦਾਹਰਨ

 

ਚੈੱਕ ਕਰੋ ਕਿ ਦਰੱਖਤ ਵਿਚ ਇਕੋ ਰਸਤੇ ਤੇ ਦੋ ਨੋਡ ਹਨ ਜਾਂ ਨਹੀਂ

ਇਹ ਵੇਖਣ ਲਈ ਪਹੁੰਚੋ ਕਿ ਦਰੱਖਤ ਵਿਚ ਦੋ ਨੋਡ ਇਕੋ ਰਸਤੇ 'ਤੇ ਹਨ ਜਾਂ ਨਹੀਂ

ਵਿਚਾਰ ਪ੍ਰਦਰਸ਼ਨ ਕਰਨਾ ਹੈ ਡੀਐਫਐਸ ਤੱਕ ਰੂਟ ਨੋਡ ਇਹ ਡੀਐਫਐਸ ਟ੍ਰਾਵਰਸਅਲ ਪਹਿਲਾਂ ਅੰਤਮ ਡੂੰਘਾਈ ਤੱਕ ਜੜ ਦੇ ਹਰੇਕ ਉਪ-ਸਮੂਹ ਨੂੰ ਵੇਖਦਾ ਹੈ, ਭਾਵ ਇਹ ਹਰ ਆਖਰੀ ਪੱਧਰੀ ਰਸਤੇ ਨੂੰ ਆਖਰੀ ਪੱਤਿਆਂ ਦੇ ਵਰਟੈਕਸ ਤੱਕ ਜਾਂਦਾ ਹੈ ਅਤੇ ਫਿਰ ਅਗਲੇ ਲੀਨੀਅਰ ਮਾਰਗ ਤੇ ਜਾਂਦਾ ਹੈ.

ਵਿਚਾਰ ਕਰੋ,

ਵਕ਼ਤ ਵਿਚ - ਇਕ ਨੋਡ ਦਾ ਸਮਾਂ ਉਹ ਸਮਾਂ ਹੁੰਦਾ ਹੈ ਜਦੋਂ ਇਹ ਰੂਟ ਨੋਡ ਤੋਂ ਸ਼ੁਰੂ ਹੋ ਰਹੇ ਡੀਐਫਐਸ ਟ੍ਰੈਵਰਸਾਲ ਨੂੰ ਪ੍ਰਦਰਸ਼ਿਤ ਕਰਨ ਵੇਲੇ ਸਭ ਤੋਂ ਪਹਿਲਾਂ ਜਾਂਦਾ ਹੈ. ਪ੍ਰਵੇਸ਼ ਦਾ ਸਮਾਂ ਡੀਐਫਐਸ ਟਰੈਵਰਸਾਲ ਦੇ ਦੌਰਾਨ ਇੱਕ ਨੋਡ ਦਾ.

ਆtimeਟਟਾਈਮ - ਨੋਡ ਦਾ ਸਮਾਂ ਉਹ ਸਮਾਂ ਹੁੰਦਾ ਹੈ ਜਦੋਂ ਇਹ ਬੱਚਿਆਂ ਦੇ ਮਿਲਣ ਤੋਂ ਬਾਅਦ ਸਭ ਦਾ ਦੌਰਾ ਕੀਤਾ ਜਾਂਦਾ ਹੈ, ਇਹ ਰੂਟ ਨੋਡ ਦੇ ਰਸਤੇ ਤੇ ਵਾਪਸ ਪਰਤਣ ਵੇਲੇ ਹੁੰਦਾ ਹੈ. ਨਿਕਾਸ ਦਾ ਸਮਾਂ ਡੀਐਫਐਸ ਟਰੈਵਰਸਾਲ ਦੇ ਦੌਰਾਨ ਇੱਕ ਨੋਡ ਦਾ.

ਜੇ ਨੋਡਸ ਇਕੋ ਮਾਰਗ ਦੇ ਨਾਲ ਖਿਆਲ ਕਰਦੇ ਹਨ:

  1. ਇਹ ਮੰਨ ਕੇ ਕਿ ਤੁਸੀਂ ਵਿ ਦੇ ਮਾਪੇ ਹੋ, u ਦੇ ਸਮੇਂ ਦਾ <intime of v & ਯੂ ਆ outਟਟਾਈਮ ਯੂ> ਆ outਟਟਾਈਮ ਵੀ.
  2. ਜਾਂ ਇਹ ਮੰਨਣਾ ਕਿ v ਤੁਹਾਡੇ ਪਿਤਾ ਹੈ ਤਾਂ, ਵਾਈ ਦਾ ਟਾਈਮ <ਯੂ ਦੇ ਅੰਦਰ ਅਤੇ ਵਾਈ ਟਾਈਮ ਵੀ> ਯੂ ਦੇ ਬਾਹਰ ਹੋਣ ਦਾ ਸਮਾਂ.
  3. ਆਮ ਤੌਰ 'ਤੇ, ਜਦੋਂ ਦੋ ਨੋਡ ਇਕੋ ਰਸਤੇ ਨਾਲ ਹੁੰਦੇ ਹਨ, ਇਕ ਮਾਂ-ਪਿਓ ਹੈ ਅਤੇ ਦੂਜਾ ਬੱਚਾ ਹੈ. ਉਸ ਸਥਿਤੀ ਵਿੱਚ ਡੀਐਫਐਸ ਟ੍ਰਾਵਰਸਲ ਦੇ ਬਾਅਦ:
    • ਮਾਪਿਆਂ ਦਾ ਸਮਾਂ <ਬੱਚੇ ਦੇ ਸਮੇਂ ਦਾ
    • ਮਾਪਿਆਂ ਦਾ ਆਉਟਟਾਈਮ> ਬੱਚੇ ਦਾ ਬਾਹਰ ਹੋਣਾ
1. Perform DFS traversal from the given root node and for each node calculate entry time and exit time using intime[ ] and outtime[ ] arrays.
2. So after the DFS traversal is complete. Process the query list q. Each query in q consists of two values u and v.
3. If intime[u] < intime[v] and also outtime[u] > outtime[v], print "YES".
4. Or if intime[v] < intime[u] and also outtume[v] > outtime[u], print "YES".
5. If conditions 3 and 4 are false, then print "NO".
6. If conditions 3 and 4 are true, this signifies that u & v lie along the same path originating from the root.
7. If condition 5 is true, then it signifies that u & v do not lie along the same path originating from the root.

ਐਲਗੋਰਿਦਮ ਨੂੰ ਹੇਠਾਂ ਦਰਸਾਇਆ ਗਿਆ ਹੈ:

ਚੈੱਕ ਕਰੋ ਕਿ ਦਰੱਖਤ ਵਿਚ ਇਕੋ ਰਸਤੇ ਤੇ ਦੋ ਨੋਡ ਹਨ ਜਾਂ ਨਹੀਂ

ਚੈੱਕ ਕਰੋ ਕਿ ਦਰੱਖਤ ਵਿਚ ਇਕੋ ਰਸਤੇ ਤੇ ਦੋ ਨੋਡ ਹਨ ਜਾਂ ਨਹੀਂ

ਕੋਡ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ ਇਹ ਵੇਖਣ ਲਈ ਕਿ ਕੀ ਦਰੱਖਤ ਵਿਚ ਦੋ ਨੋਡ ਇਕੋ ਰਸਤੇ 'ਤੇ ਹਨ

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* variable to keep track of intime 
and outtime values for each vertex */
int times = 0;

/* function to perform DFS from root nodes to all the leaves 
& calculate entry time (intime) 
& exit time (outtime) 
for each vertex */
void DFS(int root,vector <int> graph[],vector <int> &intime,vector<int> &outtime)
{
    intime[root] = ++times;
    
    for(auto i : graph[root])
        DFS(i,graph,intime,outtime);
    
    outtime[root] = ++times;
    return;
}

/* function that returns true if nodes u and v 
lie along the same path else return false */
bool query(int u,int v,vector <int> intime,vector <int> outtime)
{
    return ((intime[u] < intime[v] && outtime[u] > outtime[v]) || 
             (intime[v] < intime[u] && outtime[v] > outtime[u])); 
}

int main()
{
    /* Define
    1.number of vertices
    2.root vertex
    3.edges
    */
    int V = 9;
    int root = 0;
    vector<vector<int>> Edges = {{0,1},{1,4},{1,5},{0,2},{2,6},{6,7},{0,3},{3,8}};
    
    /* construct the graph */
    vector <int> graph[V];
    for(auto edge : Edges)
    graph[edge[0]].push_back(edge[1]);
    
    /* Define vectors that store entry time(intime) & 
    exit time(outtime) for each vertex of the tree */
    vector <int> intime(V,0);
    vector <int> outtime(V,0);
    
    /* perform DFS traversal to fill intime & outtime vectors */
    DFS(root,graph,intime,outtime);
    
    /* Define query vertices */
    vector<vector<int>> q = {{0,5},{2,7},{1,8}};
    
    for(auto i : q)
    {
        if(query(i[0],i[1],intime,outtime))
        cout<<"YES";
        else
        cout<<"NO";
        
        cout<<endl;
    }
    
    return 0;
}
YES 
YES 
NO

ਜਾਵਾ ਕੋਡ ਇਹ ਪਤਾ ਲਗਾਉਣ ਲਈ ਕਿ ਦਰੱਖਤ ਵਿਚ ਇਕੋ ਰਾਹ 'ਤੇ ਦੋ ਨੋਡ ਹਨ ਜਾਂ ਨਹੀਂ

import java.io.*;
import java.util.*;

class TutorialCup 
{
    /* variable to keep track of intime 
    and outtime values for each vertex */
    static int times = 0;
    
    /* function to perform DFS from root nodes to all the leaves 
    & calculate entry time (intime) 
    & exit time (outtime) 
    for each vertex */
    static void DFS(int root,ArrayList<ArrayList<Integer>> graph,int [] intime,int [] outtime)
    {
        intime[root] = ++times;
        
        Iterator itr = graph.get(root).iterator();
        
        while(itr.hasNext())
        {
            int i = (Integer)itr.next();
            DFS(i,graph,intime,outtime);
        }
        
        outtime[root] = ++times;

        return;
    }
    
    /* function that returns true if nodes u and v 
    lie along the same path else return false */
    static boolean query(int u,int v,int [] intime,int [] outtime)
    {
        return ((intime[u] < intime[v] && outtime[u] > outtime[v]) || 
                 (intime[v] < intime[u] && outtime[v] > outtime[u])); 
    }
    
    public static void main (String[] args)
    {
        /* Define
        1.number of vertices
        2.root vertex
        3.edges
        */
        int V = 9;
        int root = 0;
        int [][] Edges = {{0,1},{1,4},{1,5},{0,2},{2,6},{6,7},{0,3},{3,8}};
        
        /* construct the graph */
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        
        for(int i=0;i<V;i++)
        graph.add(new ArrayList<Integer>());
        
        for(int i=0; i<Edges.length; i++)
        graph.get(Edges[i][0]).add(Edges[i][1]);
        
        /* Define vectors that store entry time(intime) & 
        exit time(outtime) for each vertex of the tree */
        int [] intime = new int[V];
        int [] outtime = new int[V];
        
        /* perform DFS traversal to fill intime & outtime vectors */
        DFS(root,graph,intime,outtime);
        
        /* Define query vertices */
        int [][] q = {{0,5},{2,7},{1,8}};
        
        for(int i=0; i<q.length; i++)
        {
            if(query(q[i][0],q[i][1],intime,outtime))
            System.out.println("YES");
            else
            System.out.println("NO");
        }
    }
}
YES
YES
NO

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ

ਟੀ (ਐਨ) = ਓ (ਐਨ), ਐਨ = ਨੋਡਸ ਦੀ ਸੰਖਿਆ. ਕਿਉਂਕਿ ਅਸੀਂ ਡੀਐਫਐਸ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਹੈ ਜੋ ਕਿ ਰੁੱਖ ਵਿਚਲੇ ਨੋਡਾਂ ਤੋਂ ਪਾਰ ਲੰਘ ਗਿਆ ਹੈ. ਇਸ ਲਈ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਰੇਖਿਕ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਏ (ਐਨ) = ਓ (ਐਨ), ਇਨਟਾਈਮ [] ਅਤੇ ਆtimeਟਟਾਈਮ [] ਐਰੇ ਦੀ ਵਰਤੋਂ ਲਈ. ਇਹ ਦੋਵੇਂ ਐਰੇ ਦਾ ਆਕਾਰ ਨੋਡਾਂ ਦੀ ਗਿਣਤੀ ਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਪੁਲਾੜ ਦੀ ਜਟਿਲਤਾ ਵੀ ਲੀਨੀਅਰ ਹੈ.