Gym - 101875I I Will Go (dfs序)

题意：N个人要参加一个局，每个人有自己的好朋友，如果他的好朋友来，他才有可能来。N个人的关系不够成环。Q次查询，问若x来了，y是否肯定来。

分析：若点y是x的祖先，则y肯定回来。一次dfs确定每个点覆盖的区间，若点x的dfs序在y的覆盖区间内，则y肯定会来。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+5;

typedef long long LL;

const int INF = 0x3f3f3f3f;

struct Edge{

    int v,next;

}edges[maxn];

int tot,head[maxn],dfn;

int L[maxn],R[maxn];

int ind[maxn];

void init()

{

    memset(head,-1,sizeof(head));

    memset(ind,0,sizeof(ind));

    memset(L,0,sizeof(L));

    tot= dfn = 0;

}

void AddEdge(int u,int v)

{

    edges[tot] = (Edge){v,head[u]};

    head[u] = tot++;

}

void dfs(int u)

{

    L[u] = ++dfn;

    for(int i=head[u];~i;i=edges[i].next){

        int v = edges[i].v;

        dfs(v);

    }

    R[u] = dfn;

}

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int st,N,M;

    int u,v,tmp;

    while(scanf("%d %d",&N,&M)==2){

        init();

        for(int i =1;i<=N;++i){

            scanf("%d",&u);

            if(u==-1) continue;

            u++;

            AddEdge(u,i);

            ind[i]++;

        }

        for(int i=1;i<=N;++i){

            if(!ind[i]) dfs(i);

        }

        while(M--){

            scanf("%d %d",&u,&v);

            u++,v++;

            //cout<<L[v]<<" "<<R[v]<<endl;

            if(L[u]>=L[v] && L[u]<=R[v]) printf("Yes\n");

            else printf("No\n");

        }

    }

    return 0;

}

巴特西

Gym - 101875I I Will Go (dfs序)

最新文章

热门文章