Untitled

mail@pastecode.io avatarunknown
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;
}