შეამოწმეთ, არის თუ არა ორი კვანძი ერთ გზაზე


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon ფაქტები Fourkites Samsung
სიღრმისეული პირველი ძებნა Graph დიაგრამაზე გადასვლა

პრობლემის განცხადება

პრობლემა "შეამოწმეთ არის თუ არა ორი კვანძი ხეზე იმავე გზაზე" აცხადებს, რომ თქვენ გეძლევათ a n-ary ხე (მიმართული აციკლური გრაფიკი) ფესვებიდან root კვანძი ერთ მიმართულებითი კიდეები მის წვერებს შორის. ასევე მოცემულია მოთხოვნების სია q.

  1. Q სიაში თითოეული მოთხოვნა შედგება ორი წვერისაგან u & v.
  2. თქვენ უნდა დაბეჭდოთYES”თუ კვანძები თქვენ და იმავე გზაზე იტყუებით წარმოშობით root მწვერვალი
  3. სხვა ბეჭდვაარა”თუ კვანძები თქვენ და სხვა სხვადასხვა ბილიკზე იწექით წარმოშობით root მწვერვალი

მაგალითი

 

შეამოწმეთ, არის თუ არა ორი კვანძი ერთ გზაზე

მიდგომა იმის შესამოწმებლად, არის თუ არა ორი კვანძი ერთ გზაზე

იდეა არის შესრულება DFS საწყისი root კვანძი ეს DFS ტრავერსალი პირველად ეწვევა ფესვის თითოეულ ქვეძეს ბოლო სიღრმემდე, რაც ნიშნავს, რომ იგი ეწვევა თითოეულ უნიკალურ ხაზოვან გზას ბოლო ფოთლის მწვერვალამდე და შემდეგ გადადის შემდეგ ხაზოვან გზაზე.

განვიხილოთ,

Close - კვანძის დრო არის დრო, როდესაც მას პირველად სტუმრობენ DFS გადაკვეთის შესრულებისას, დაწყებული root კვანძიდან, ეს არის შესვლის დრო კვანძის DFS გავლის დროს.

დროგარეშე - კვანძის დრო არ არის ის დრო, როდესაც მას სტუმრობენ მას შემდეგ, რაც მას შვილები მოინახულებენ, ეს ხდება ფესვის კვანძისკენ მიმავალ გზაზე დაბრუნებისას გასვლის დრო კვანძის DFS გავლის დროს.

თუ u & v კვანძები იმავე ბილიკზე მდებარეობს:

  1. ვთქვათ, რომ შენ 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 გავლის შემდეგ:
    • intime მშობლის <intime ბავშვი
    • მშობლის outtime> ბავშვის outtime
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), intime [] და outtime [] მასივების გამოსაყენებლად. ამ ორივე მასივის ზომა დამოკიდებულია კვანძების რაოდენობაზე. ამრიგად, სივრცის სირთულე ასევე ხაზოვანია.