Untitled
c_cpp
a month ago
823 B
1
Indexable
Never
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+7; vector<int> adj[maxn]; bool mark[maxn]; int timer , ed[maxn] , st[maxn]; void dfs(int u){ st[u] = ++timer; //cout << st[u] ; mark[u] = true; for(auto w : adj[u]){ if(!mark[w]){ //timer++; dfs(w); } } ed[u] = timer; // cout << ed[u] << ' '; } int main(){ int m; cin >> m; for(int i = 0 ; i < m ; i++){ int u , v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(1); int u , v; cin >> u >> v; // weather v is in the subtree of u or not //cout << ed[u] << ' ' << ed[v] << ' '; if(st[u] <= st[v] && ed[v] <= ed[u]) cout << "YES\n"; else cout << "NO\n"; return 0; }