በአንድ ዛፍ ውስጥ ሁለት አንጓዎች በተመሳሳይ መንገድ ላይ መሆናቸውን ያረጋግጡ  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፋርስት አራት ኪይትስ ሳምሰንግ
ጥልቀት የመጀመሪያ ፍለጋ ግራፍ ግራፍ ትራቫርስል

የችግሩ መግለጫ  

ችግሩ “ሁለት አንጓዎች በአንድ ዛፍ ላይ በተመሳሳይ መንገድ ላይ መሆናቸውን ያረጋግጡ” የሚለው እንደተሰጠዎት ሀ n-ary ዛፍ (የታተመ የቢስክሌት ግራፍ) ስር የሰደደ ሥር መስቀለኛ መንገድ ከ ዩኒ-አቅጣጫዊ በጠርዙ ጫፎች መካከል ጫፎች ፡፡ እንዲሁም የጥያቄዎች ዝርዝር ይሰጥዎታል q.

  1. በዝርዝር ውስጥ ያለው እያንዳንዱ ጥያቄ ሁለት ጫፎችን ዩ & ቁ.
  2. ማተም አለብዎትአዎ”አንጓዎች ከሆኑ u & v በተመሳሳይ መንገድ ላይ ይተኛሉሥር ጫፍ።
  3. ሌላ ህትመት “አይ”አንጓዎች ከሆኑ u & v በተለያዩ መንገዶች ይዋሻሉሥር ጫፍ።

ለምሳሌ  

 

በአንድ ዛፍ ውስጥ ሁለት አንጓዎች በተመሳሳይ መንገድ ላይ መሆናቸውን ያረጋግጡ

በአንድ ዛፍ ውስጥ ሁለት አንጓዎች በአንድ መንገድ ላይ ካሉ ለመፈተሽ አቀራረብ  

ሀሳቡ ማከናወን ነው DFSሥር መስቀለኛ መንገድ ይህ የዲኤፍ.ኤስ ማቋረጫ መጀመሪያ እስከ መጨረሻው ጥልቀት ድረስ እያንዳንዱን ሥሩ ንዑስ ክፍል ይጎበኛል ፣ ማለትም እስከ መጨረሻው ቅጠሉ ጫፍ ድረስ እያንዳንዱን ልዩ መስመራዊ መንገድን ይጎበኛል ከዚያም ወደ ቀጣዩ መስመራዊ መንገድ ይሄዳል ማለት ነው ፡፡

እስቲ አስብ ፣

በጊዜው - የመስቀለኛ ክፍል መጀመሪያ ከስር መስቀለኛ መንገድ ጀምሮ የ DFS ን ማቋረጥ ሲያከናውን በመጀመሪያ የሚጎበኝበት ጊዜ ነው ፡፡ የመግቢያ ሰዓት በዲኤፍኤስ ማቋረጫ ወቅት የመስቀለኛ ክፍል ፡፡

የስራ ሰዓት - የመስቀለኛ መንገድ ልጆች ሁሉ ከተጎበኙ በኋላ የሚጎበኙበት ጊዜ ነው ፣ ይህ የሚሆነው ወደ ስር መስቀለኛ መንገድ በሚመለስበት ጊዜ ነው ፣ መውጫ ሰዓት በዲኤፍኤስ ማቋረጫ ወቅት የመስቀለኛ ክፍል ፡፡

ተመልከት
ክሩሽካል አልጎሪዝም

አንጓዎች በተመሳሳይ መንገድ ላይ ቢተኙ:

  1. እርስዎ የዚያን ጊዜ ወላጅ እንደሆኑ መገመት ፣ intime of u <intime of ቁ & u of out> of out of v.
  2. ወይም ደግሞ የዚያን ጊዜ ወላጅ ነኝ ብሎ ማሰብ ፣ intime of v <intime of u & outtime of v> outtime of u.
  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.

ስልተ ቀመሩ ከዚህ በታች ቀርቧል

በአንድ ዛፍ ውስጥ ሁለት አንጓዎች በተመሳሳይ መንገድ ላይ መሆናቸውን ያረጋግጡ

በአንድ ዛፍ ውስጥ ሁለት አንጓዎች በተመሳሳይ መንገድ ላይ መሆናቸውን ያረጋግጡ

ኮድ  

የ 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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ቲ (n) = O (n) ፣ n = የአንጓዎች ብዛት። ምክንያቱም በዛፉ ውስጥ ባሉ አንጓዎች ላይ የተሻገረውን ዲ.ኤፍ.ኤስ ተጠቅመናል ፡፡ ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው ፡፡

ተመልከት
ቢ.ኤፍ.ኤፍ.ኤስ ለተቋረጠ ግራፍ

የቦታ ውስብስብነት

A (n) = O (n) ፣ የጊዜime [] እና ጊዜያዊ [] ዝግጅቶችን ለመጠቀም ፡፡ እነዚህ ሁለቱም ድርድሮች መጠናቸው በመስቀሎች ብዛት ላይ የተመሠረተ ነው። ስለዚህ የቦታ ውስብስብነት እንዲሁ መስመራዊ ነው።