原题解链接：https://ac.nowcoder.com/discuss/150263

强连通分量+并查集

时间复杂度O(M)O(M)

由于情况非常的复杂，考虑一次性判断完所有情况，可能会写的非常的累。

于是我们可以分成三次检查，每次检查只检查一部分不合法的情况。

第一次强连通算法的检查:

强连通算法跑出来之后,如果存在一个强连通分量中有一些成员拥有照片和一些成员没有即为不合法，如果超过一个强连通分量里有人拥有照片也是不合法。

第二次并查集检查:

对于每一条两个端点都是拥有照片的人的边。我们合并这条边的两个端点。

然后依此合并完，如果所有拥有照片的人无法合并到一个集合中，那么我们认为也是不合法。

第三次检查, DFS 检查

如果每一个人拥有照片之后，DFS 到的后继节点没有照片,那么也是不合法的。

如果通过三次检查我们就认为是可行的,不然就是有人在说谎。

上述三重检查,存在一些重复判断,两个判断之间会存在一些重复部分，其实完全可以写在一次DFS过程中，使得代码非常的优雅。

但是那样写需要比较好的代码能力。但是拆成三次检查,就会降低代码编写的难度，但是会造成代码长度过长，而且也会比较臃肿,所以具体 采取哪种写法，任凭选择。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int i,i0,n,m,T,dfn[maxn],low[maxn],deep,col[maxn],sum,in[maxn],r[maxn],rc[maxn],cnt[maxn],cnts;
bool vis[maxn],f;
vector<int>mp[maxn],mp0[maxn],v;
stack<int>stk;
queue<int>q;
void dfs(int now)
{
    dfn[now]=low[now]=++deep;
    stk.push(now);
    vis[now]=1;
    for(auto i:mp[now])
    {
        if(!dfn[i])
        {
            dfs(i);
            low[now]=min(low[now],low[i]);
        }
        else if(vis[i])low[now]=min(low[now],low[i]);
    }
    if(dfn[now]==low[now])
    {
        sum++;
        while(vis[now])
        {
            col[stk.top()]=sum;
            vis[stk.top()]=0;
            stk.pop();
        }
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)scanf("%d",&r[i]);
        sum=deep=0;
        for(i=1;i<=n;i++)mp[i].clear(),dfn[i]=0,in[i]=0,rc[i]=0;
        while(m--)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            mp[a].push_back(b);
        }
        for(i=1;i<=n;i++)if(!dfn[i])dfs(i);
        f=1;
        for(i=1;i<=sum;i++)mp0[i].clear();
        for(i=1;i<=n;i++)
        {
            for(auto i0:mp[i])if(col[i0]!=col[i])in[col[i0]]++,mp0[col[i]].push_back(col[i0]),cnt[col[i0]]++;
            if(r[i])rc[col[i]]=1;
        }
        for(i=1;i<=n;i++)if(r[i]!=rc[col[i]])f=0;
        v.clear();
        for(i=1;i<=sum;i++)if(!cnt[i])q.push(i);
        while(!q.empty())
        {
            m=q.front(),q.pop();
            v.push_back(m);
            for(auto i:mp0[m])if(!--cnt[i])q.push(i);
        }
        cnts=0;
        for(auto i:v)
        {
            if(rc[i]&&!vis[i])cnts++;
            if(!rc[i]&&vis[i])f=0;
            if(rc[i])for(auto i0:mp0[i])vis[i0]=1;
        }
        for(auto i:v)vis[i]=0;
        if(f&&cnts<2)printf("hahaha\n");
        else printf("yinyinyin\n");
    }
    return 0;
}