두 노드가 트리에서 동일한 경로에 있는지 확인

난이도 중급
자주 묻는 질문 아마존 팩트 셋 포카이트 삼성
깊이 우선 검색 Graph 그래프 순회조회수 20

문제 정책

"두 개의 노드가 트리에서 동일한 경로에 있는지 확인"문제는 n 항 트리 (directed acyclic graph) 뿌리 뿌리 노드 단방향 정점 사이의 가장자리. 또한 쿼리 목록이 제공됩니다. q.

  1. 목록 q의 각 쿼리는 두 개의 꼭지점 u 및 v로 구성됩니다.
  2. ”if 노드 u와 v는 같은 길을 따라 누워 유래 뿌리 꼭지점.
  3. Else print“아니”if 노드 u & v는 다른 길을 따라 누워 유래 뿌리 꼭지점.

 

두 노드가 트리에서 동일한 경로에 있는지 확인

두 노드가 트리에서 동일한 경로에 있는지 확인하는 방법

아이디어는 수행하는 것입니다 DFS뿌리 마디. 이 DFS 순회는 먼저 마지막 깊이까지 루트의 각 하위 트리를 방문합니다. 즉, 마지막 리프 정점까지 각 고유 선형 경로를 방문한 다음 다음 선형 경로로 이동합니다.

중히 여기다,

제 시간에 – 노드의 intime은 루트 노드에서 시작하여 DFS 순회를 수행하는 동안 처음 방문한 시간입니다. 입장 시간 DFS 순회 중 노드의.

외출 – 노드의 아웃 타임은 모든 자식이 방문한 후 방문한 시간입니다. 이것은 루트 노드로 향하는 경로를 따라 돌아 오는 동안 발생합니다. 종료 시간 DFS 순회 중 노드의.

노드 u & v가 동일한 경로를 따라있는 경우 :

  1. u가 v의 부모라고 가정하면 intime of u <intime of v & u의 아웃 타임> v의 아웃 타임.
  2. 또는 v가 u의 부모라고 가정하면 v의 intime <u의 intime & v의 outtime> u의 outtime.
  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 [] 배열 사용. 이 두 어레이의 크기는 노드 수에 따라 다릅니다. 따라서 공간 복잡성도 선형입니다.

Translate »