Праверце, ці знаходзяцца два дрэвы на адным шляху ў дрэве


Узровень складанасці серада
Часта пытаюцца ў амазонка Факты Фуркайты Samsung
Глыбіня Першы пошук Графік Абход графіка

Пастаноўка праблемы

Праблема "Праверыць, ці знаходзяцца два дрэвы на адным шляху ў дрэве", абвяшчае, што вам дадзена п-рые дрэва (накіраваны ацыклічны графік) караніцца ў корань вузел з аднанакіраваны краю паміж вяршынямі. Вам таксама дадзены спіс запытаў q.

  1. Кожны запыт у спісе q складаецца з дзвюх вяршынь u & v.
  2. Вы павінны надрукаваць “ДА”Калі вузлы u & v ляжаць па адным шляху які паходзіць з корань вяршыня.
  3. Іншы прынт “НЕ”Калі вузлы u & v ляжаць па розных шляхах які паходзіць з корань вяршыня.

Прыклад

 

Праверце, ці знаходзяцца два дрэвы на адным шляху ў дрэве

Падыход, каб праверыць, ці знаходзяцца два дрэвы на адным шляху ў дрэве

Ідэя складаецца ў тым, каб выступіць DFS ад корань вузел. Гэта праходжанне DFS спачатку наведвае кожнае паддрэва кораня да апошняй глыбіні, гэта значыць, што яно наведвае кожны ўнікальны лінейны шлях да апошняй вяршыні ліста, а затым пераходзіць да наступнага лінейнага шляху.

Разгледзім,

У час - час працы вузла - гэта час, у які ён быў наведаны першым падчас выканання DFS-абходу, пачынаючы з каранёвага вузла, гэта час уваходу вузла падчас абходу DFS.

Па-за часам - непрацаздольнасць вузла - гэта час, падчас якога ён наведваецца пасля наведвання ўсіх яго дзяцей, гэта адбываецца пры вяртанні па шляху да каранёвага вузла, гэта час выхаду вузла падчас абходу DFS.

Калі вузлы u & v ляжаць па адным шляху:

  1. мяркуючы, што u з'яўляецца бацькам v, тады, intime of u <intime of v & outtime of u> outtime of v.
  2. Або мяркуючы, што v з'яўляецца бацькам і тады, 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

Код Java для пошуку Праверце, ці знаходзяцца два дрэвы на адным шляху ў дрэве

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), для выкарыстання масіваў intime [] і outtime []. Памер абодвух масіваў залежыць ад колькасці вузлоў. Такім чынам, касмічная складанасць таксама лінейная.