链接：

来源：牛客网

通知小弟

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

在战争时期，A国派出了许多间谍到其他国家去收集情报。因为间谍需要隐秘自己的身份，所以他们之间只是单向联系。所以，某个间谍只能单向联系到一部分的间谍。同时，间谍也不知道跟他联系的是谁。

HA是间谍们的老大，但他也只能联系到部分的间谍。HA现在有一项命令有告诉所有的间谍。HA想要知道他至少要告诉多少个他能联系上的间谍才能通知到所有的间谍。

输入描述:

有多个测试数据。

对于每个测试数据：

第一行为一个整数n，m（0 < n,m<=500）代表间谍的数量和HA能通知到的间谍的

数量（间谍的编号为1-n）；

第二行为m个用空格隔开的整数xi,代表HA能通知到的间谍的编号；

第三行到第n+2行，每一行第一个整数ai(0 < =ai < n)表示第i-2个间谍能单向联系到的间谍数。之后有ai个用空格隔开的整数，表示间谍i-2能单向联系到的间谍的编号。

输出描述:

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

示例1

输入

3 2

1 2

1 2

1 1

0

输出

-1

示例2

输入

3 1

1

2 2 3

0

0

输出

1

有向图缩点成DAG（有向无环图）的水题。用到的算法是求有向图的强连通分量。

一、

题目的意思是 小弟 之间构成一个有向图，然后BOSS 可以直接通知给定的几个小弟。

问最少通知几个小弟，使得所有人被间接通知到。

转化一下就是

- 从BOSS这个点，最少连几条边可以让整个图连通

就像用一个根节点让一个森林变成一颗树一样，只要把森林里所有树的根结点连接起来即可

所以 如果小弟组成的是一系列的DAG，那么只要连接所有DAG的第一个结点即可

#include
    
     #include
     
      #include
      
       using namespace std;/** Tarjan算法* 复杂度O(N+M)*/const int MAXN = 510;//点数const int MAXM = 250000;//边数 至少开n(n-1)/2，const int N = 510; //缩点后的点数struct Edge{    int to,next;}edge[MAXM];int head[MAXN],tot;int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~sccint Index,top;int scc;//强连通分量的个数bool Instack[MAXN];int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc            //num数组不一定需要，结合实际情况void addedge(int u,int v){    edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;}void Tarjan(int u){    int v;    Low[u] = DFN[u] = ++Index;    Stack[top++] = u;    Instack[u] = true;    for(int i = head[u];i != -1;i = edge[i].next)    {        v = edge[i].to;        if( !DFN[v] )        {            Tarjan(v);            if( Low[u] > Low[v] )Low[u] = Low[v];        }        else if(Instack[v] && Low[u] > DFN[v])        Low[u] = DFN[v];    }    if(Low[u] == DFN[u])    {        scc++;        do        {            v = Stack[--top];            Instack[v] = false;            Belong[v] = scc;            num[scc]++;        }        while( v != u);    }}void solve(int N){    memset(DFN,0,sizeof(DFN));    memset(Instack,false,sizeof(Instack));    memset(num,0,sizeof(num));    Index = scc = top = 0;    for(int i = 1;i <= N;i++)        if(!DFN[i])            Tarjan(i);}void init(){    tot = 0;    memset(head,-1,sizeof(head));}int G[N][N];//缩点后的图int B[N];//存放BOSS可选择的结点int main(){    int n,m;    while(cin>>n>>m)    {        init();        for(int i=0;i
       
        >B[i];        }        for(int i=1;i<=n;i++)        {            int cnt;cin>>cnt;            while(cnt--)            {                int tp;cin>>tp;                addedge(i,tp);            }        }        solve(n);        memset(G,0,sizeof(G));        /*         *遍历所有Belong[u]，建立新的图         */        for(int u=1;u<=n;u++)        {            int fg=head[u];            while(fg!=-1)//邻接表的访问方法，也可以写成            //for(int i=head[u];i!=-1;i=edge[i].next)            {                Edge &e = edge[fg];                int v = e.to;                //cout<<"Belong["<
        <<"]="<
         
          <