【题解】bzoj 4478 [Jsoi2013]侦探jyy

原题传送门

弱智搜索题

我们就枚举每个点，先判断它是否必须发生，如果没有必须发生，开始搜索它的祖先，如果祖先中有必须发生的，那么它就必须发生，如果祖先中没有必须发生的，那么搜索所有入度为0的点（除了它的祖先），搜完之后如果还有没被搜到的必须发生的事件，那么它也必须发生

#include <bits/stdc++.h>

#define N 1005

#define M 100005

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

struct node{

    int to,next;

}e1[M],e2[M];

int head1[N],head2[N],cnt1=0,cnt2=0,in[N];

inline void add1(register int u,register int v)

{

    e1[++cnt1]=(node){v,head1[u]};

    head1[u]=cnt1;

    ++in[v];

}

inline void add2(register int u,register int v)

{

    e2[++cnt2]=(node){v,head2[u]};

    head2[u]=cnt2;

}

int n,m,d;

int a[N],ans[N],tot=0,mu[N],tic=0,vis[N];

inline bool check(register int x)

{

    ++tic;

    queue<int>q;

    q.push(x);

    vis[x]=tic;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(register int i=head2[u];i;i=e2[i].next)

        {

            int v=e2[i].to;

            if(vis[v]!=tic)

            {

                q.push(v);

                vis[v]=tic;

            }

        }

    }

    for(register int i=1;i<=d;++i)

        if(vis[a[i]]==tic)

            return true;

    for(register int i=1;i<=n;++i)

        if(!in[i]&&vis[i]!=tic)

            q.push(i),vis[i]=tic;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(register int i=head1[u];i;i=e1[i].next)

        {

            int v=e1[i].to;

            if(vis[v]!=tic)

            {

                q.push(v);

                vis[v]=tic;

            }

        }

    }

    for(register int i=1;i<=d;++i)

        if(vis[a[i]]!=tic)

            return true;

    return false;

}

int main()

{

    n=read(),m=read(),d=read();

    for(register int i=1;i<=m;++i)

    {

        int u=read(),v=read();

        add1(u,v),add2(v,u);

    }

    for(register int i=1;i<=d;++i)

        a[i]=read(),mu[a[i]]=true;

    for(register int i=1;i<=n;++i)

        if(mu[i]||check(i))

            ans[++tot]=i;

    for(register int i=1;i<=tot;++i)

        write(ans[i]),putchar(' ');

    return 0;

}