📝 문제 정보#
🧐 관찰 및 접근#
- $A_{left} < B_{left} < B_{right} < A_{right}$라면 두 노드를 포함관계라고 한다.
- 이는 트리를 dfs적으로 접근하면서, 트리에 들어가는 시간 / 나가는 시간을 기록함으로써 얻어낼 수 있다.
💻 풀이#
- 코드 (C++):
int N;
vector<int> links[100010];
int start[100010], ed[100010];
int timer = 1;
void dfs(int cur, int par){
start[cur] = timer++;
for(auto nxt: links[cur]) if(nxt != par) dfs(nxt, cur);
ed[cur] = timer++;
}
void solve(){
cin >> N;
rep(i, 0, N){
int node; cin >> node;
while(true){
int x; cin >> x;
if(x == -1) break;
links[node].push_back(x);
}
sort(all(links[node]));
}
int S; cin >> S;
dfs(S, -1);
rep(i, 1, N+1) cout << i << ' ' << start[i] << ' ' << ed[i] << '\n';
}