[그래프]Euler Tour

Euler Tour(오일러 투어)

DFS를 이용하여 토리의 각 정점의 조상-자손 관계를 쉽게 찾도록 해주는 기법

설명

트리를 순회하면서 새로운 정점에 방문할 때 inOrder 번호를 부여한다.
정점에서 빠져나올 때 outOrder 번호를 부여한다.

예시 코드

typedef struct euler{
    int inOrder, outOrder;
}euler;

#define MAX_SIZE 100000
vector<int> adj[MAX_SIZE];

euler order[MAX_SIZE];
int id = 0;

void dfs(int node){
    order[node].inOrder = ++id;
    for(int i = 0; i < adj[node].size(); i++){
        dfs(adj[node][i]);
    }
    order[node].outOrder = id;
}