קאָנטראָלירן צי צוויי נאָודז זענען אויף דער זעלביקער וועג אין אַ בוים


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן פאַקסעט פאָורקיטעס סאַמסונג
דעפּט ערשטער זוך גראַפיק גראַפיק טראַווערסאַל

פּראָבלעם סטאַטעמענט

די פּראָבלעם "קוק אויב צוויי נאָודז זענען אויף דער זעלביקער וועג אין אַ בוים" שטאַטן אַז איר האָט געגעבן אַ N- אַרי בוים (דירעקטעד אַסיקליק גראַפיק) איינגעווארצלט ביי וואָרצל נאָדע מיט יוני-דירעקטיאָנאַל עדזשאַז צווישן עס ס ווערטיסעס. איר אויך באַקומען אַ רשימה פון קוויריז ק.

  1. יעדער אָנפֿרעג אין רשימה ק באשטייט פון צוויי ווערטיסעס יו.
  2. איר מוזט דרוקן “יאָ”אויב נאָודז אין דער זעלביקער וועג ערידזשאַנייטינג פון וואָרצל ווערטעקס.
  3. אלזא דרוקן “NO”אויב נאָודז איר ליגן אויף פאַרשידענע פּאַטס ערידזשאַנייטינג פון וואָרצל ווערטעקס.

בייַשפּיל

 

קאָנטראָלירן צי צוויי נאָודז זענען אויף דער זעלביקער וועג אין אַ בוים

צוגאַנג צו קאָנטראָלירן צי צוויי נאָודז זענען אויף דער זעלביקער וועג אין אַ בוים

דער געדאַנק איז צו דורכפירן דפס פון וואָרצל נאָדע. דער דפס דורך די ערשטע וויזיץ יעדער סובטרעע פון ​​דער שורש ביז די לעצטע טיפקייַט, וואָס מיינען אַז עס באזוכט יעדער יינציק לינעאַר דרך ביז די לעצטע בלאַט ווערטעקס און דאַן גייט צו דער ווייַטער לינעאַר דרך.

באַטראַכטן,

אין צייט - די ינטימע פון ​​אַ נאָדע איז דער צייט אין וואָס עס איז ערשטער באזוכט בשעת דורכפירן דפס דורך די סטאַרטינג פון וואָרצל נאָדע. פּאָזיציע צייט פון אַ נאָדע בעשאַס דפס טראַווערסאַל.

אָוטטימע - אָוטטימע פון ​​אַ נאָדע איז די צייט אין וואָס עס איז באזוכט נאָך אַלע די קינדער האָבן שוין באזוכט. דאָס כאַפּאַנז בשעת צוריקקומען אויף די וועג צו וואָרצל נאָדע. אַרויסגאַנג צייט פון אַ נאָדע בעשאַס דפס טראַווערסאַל.

אויב נאָודז u & v ליגן אויף דער זעלביקער וועג:

  1. אויב איר זענט אַ פאָטער פון V, intime of u <intime of v & אָוטטימע פון ​​ו> אָוטטימע פון ​​וו.
  2. אָדער אויב איך איז אַ פאָטער פון איר, intime of v <intime of u & outtime of v> outtime of u.
  3. בכלל, ווען צוויי נאָודז ליגן אויף דער זעלביקער וועג, איינער איז פאָטער און אנדערע איז קינד. אין דעם פאַל נאָך DFS דורך:
    • ינטימע פון ​​פאָטער <ינטימע פון ​​קינד
    • אָוטטימע פון ​​פאָטער> אָוטטימע פון ​​קינד
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.

די אַלגערידאַם איז דיפּיקטיד אונטן:

קאָנטראָלירן צי צוויי נאָודז זענען אויף דער זעלביקער וועג אין אַ בוים

קאָנטראָלירן צי צוויי נאָודז זענען אויף דער זעלביקער וועג אין אַ בוים

קאָדעקס

C ++ פּראָגראַם צו קאָנטראָלירן אויב צוויי נאָודז זענען אויף דער זעלביקער וועג אין אַ בוים

#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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

T (n) = O (n), n = נומער פון נאָודז. ווייַל מיר האָבן געוויינט DFS וואָס איז דורכגעקאָכט איבער די נאָודז אין דעם בוים. די צייט קאַמפּלעקסיטי איז לינעאַר.

ספעיס קאַמפּלעקסיטי

A (n) = O (n), פֿאַר ניצן ינטימע [] און אָוטטימע [] ערייז. ביידע די גרייס פון די ערייז איז אָפענגיק אויף די נומער פון נאָודז. אזוי די פּלאַץ קאַמפּלעקסיטי איז אויך לינעאַר.