Модны хоёр зангилаа нэг зам дээр байгаа эсэхийг шалгана уу


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Factset Фуркайт Samsung
Гүнзгий анхны хайлт График Графикийн хөндлөн огтлол

Асуудлын мэдэгдэл

"Модонд хоёр зангилаа нэг зам дээр байгаа эсэхийг шалга" гэсэн асуудалд танд a гэж заасан байгаа n-ary мод (чиглүүлсэн цикл график) үндэслэсэн эх зангилаа нэг чиглэлтэй оройнуудын хоорондох ирмэгүүд. Мөн танд асуулгын жагсаалтыг өгсөн q.

  1. Q жагсаалтын асуулт бүр u & v гэсэн хоёр оройноос бүрдэнэ.
  2. Та “YES”Бол зангилаа u & v ижил замаар явдаг гаралтай эх орой.
  3. Бусад хэвлэмэл “Үгүй”Бол зангилаа u & v янз бүрийн замаар явдаг гаралтай эх орой.

Жишээ нь

 

Модны хоёр зангилаа нэг зам дээр байгаа эсэхийг шалгана уу

Модонд хоёр зангилаа нэг зам дээр байгаа эсэхийг шалгах арга

Санаа бол тоглолт хийх DFS нь эх зангилаа. Энэхүү DFS хөндлөн огтлол нь эхлээд үндэсний дэд мод бүр дээр хамгийн сүүлчийн гүн хүртэл зочилдог бөгөөд энэ нь өвөрмөц шугаман зам тус бүрт сүүлчийн навчны орой хүртэл очоод дараачийн шугаман зам руу шилжинэ гэсэн үг юм.

Авч үзье,

Цагтаа - зангилааны intime гэдэг нь root зангилаанаас эхлээд DFS дамжуулалтыг хийж байхдаа зочлох цаг юм. орох цаг DFS дамжуулалтын үед зангилааны.

Ажлын бус цаг - зангилааны завсарлага гэдэг нь хүүхдүүд очсоны дараа зочлох цаг юм. гарах цаг DFS дамжуулалтын үед зангилааны.

Хэрэв u & v зангилаа ижил замаар хэвтэж байвал:

  1. Хэрэв та v-ийн эцэг эх гэж тооцвол, intime of u <intime of v & utime of u> v out of v.
  2. Эсвэл v-г угийн эцэг гэж үзвэл, intime of v <intime of u & out of of v> outtime u.
  3. Ерөнхийдөө, хоёр зангилаа нэг зам дээр хэвтэхэд нэг нь эцэг эх, нөгөө нь хүүхэд. Энэ тохиолдолд DFS дамжуулалтын дараа:
    • intime of parent <intime of child
    • эцэг эхийн гадуур ажиллах хугацаа> хүүхдийн хоцрогдол
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-ийг ашигласан болно. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь шугаман юм.

Сансрын нарийн төвөгтэй байдал

Intime [] ба outtime [] массивыг ашиглахад зориулсан A (n) = O (n). Эдгээр массивын хэмжээ нь зангилааны тооноос хамаарна. Тиймээс орон зайн нарийн төвөгтэй байдал нь мөн шугаман юм.