2018年牛客网寒假多校赛第四场 E题 通知小弟 【有向图求强连通缩点】

链接：https://www.nowcoder.net/acm/contest/76/E
来源：牛客网

题目描述
在战争时期，A国派出了许多间谍到其他国家去收集情报。因为间谍需要隐秘自己的身份，所以他们之间只是单向联系。所以，某个间谍只能单向联系到一部分的间谍。同时，间谍也不知道跟他联系的是谁。
HA是间谍们的老大，但他也只能联系到部分的间谍。HA现在有一项命令有告诉所有的间谍。HA想要知道他至少要告诉多少个他能联系上的间谍才能通知到所有的间谍。
输入描述:

有多个测试数据。
对于每个测试数据：
第一行为一个整数n，m（0 < $<$n,m ≤ $\le$500）代表间谍的数量和HA能通知到的间谍的数量（间谍的编号为1-n）；
第二行为m个用空格隔开的整数xi,代表HA能通知到的间谍的编号；
第三行到第n+2行，每一行第一个整数ai(0 ≤ $\le$ai < $<$n)表示第i-2个间谍能单向联系到的间谍数。之后有ai个用空格隔开的整数，表示间谍i-2能单向联系到的间谍的编号。

输出描述:

输出一行，此行中有一个整数，代表HA至少需要联系的间谍数。如果HA不能通知到所有间谍，输出-1。

示例1
输入

3 2
1 2
1 2
1 1
0

输出

-1

分析，我们看到这个题很容易想到，给你一个有向图，问你最少通知多少个人，如果是有向无环图，那么我们只要看，每一个入度为0的点【其他人都不能通知到这些人】是否都被通知到了，就能判断是否每个人都被通知到了，那么，如果其中有环的话，那么只要通知其中一个人，那么环中的每个人都被通知到了，这样我们就可以想到，通过把这个环缩点成一个人，这样就能够变成一个有向无环图，再去找缩点之后的入度为0的点就行了

代码如下

#include<bits/stdc++.h>
#define cl(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
vector<int>g[maxn];
int dfn[maxn];
int low[maxn];
int cnt,scc,top;
int id[maxn];
int in[maxn];
int sta[maxn];
int can[maxn];
bool mark[maxn];//判断是否在栈中
int vis[maxn];
int n,m;
void init()
{
    cl(dfn,0);
    cl(low,0);
    cl(id,0);
    cl(in,0);
    cl(can,0);
    cl(sta,0);
    cl(mark,false);
    cl(vis,0);
    scc=top=cnt=0;
}
void tarjan(int u)
{
    dfn[u]=low[u]=cnt++;
    sta[top++]=u;
    mark[u]=true;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(mark[v])
        {
            low[u]=min(low[u],low[v]);
        }
    }
    if(low[u]==dfn[u])
    {
        scc++;
        int v;
        do
        {
            v=sta[--top];
            mark[v]=false;
            id[v]=scc;
        }while(u!=v);
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {

        init();
        int ans=0;
        for(int i=0;i<=n;i++)
        {
            g[i].clear();
        }
        for(int i=1;i<=m;i++)
        {
            int x;
            scanf("%d",&x);
            can[x]=1;
        }
        for(int i=1;i<=n;i++)
        {
            int k;
            scanf("%d",&k);
            for(int j=1;j<=k;j++)
            {
                int y;
                scanf("%d",&y);
                g[i].push_back(y);
            }
        }
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])
                tarjan(i);
        }
        for(int i=1;i<=n;i++)
        {
              for(int j=0;j<g[i].size();j++)
            {
                int v=g[i][j];
                if(id[i]!=id[v])
                {
                    in[id[v]]++;
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(can[i])
            {
                vis[id[i]]=1;
            }
        }
        for(int i=1;i<=scc;i++)
        {
            if(!vis[i]&&!in[i])
            {
                flag=0;
                break;
            }
            else if(!in[i]&&vis[i])
            {
                ans++;
            }
        }
        printf("%d\n",flag?ans:-1);
    }
    return 0;
}