学步园

南阳理工学院共有M个系，分别编号1~M,其中各个系之间达成有一定的协议，如果某系有新软件可用时，该系将允许一些其它的系复制并使用该软件。但该允许关系是单向的，即：A系允许B系使用A的软件时，B未必一定允许A使用B的软件。

现在，请你写一个程序，根据各个系之间达成的协议情况，计算出最少需要添加多少个两系之间的这种允许关系，才能使任何一个系有软件使用的时候，其它所有系也都有软件可用。

输入

第一行输入一个整数T，表示测试数据的组数(T<10)
每组测试数据的第一行是一个整数M，表示共有M个系(2<=M<=100)。
随后的M行，每行都有一些整数，其中的第i行表示系i允许这几个系复制并使用系i的软件。每行结尾都是一个0，表示本行输入结束。如果某个系不允许其它任何系使用该系软件，则本行只有一个0.

输出

对于每组测试数据，输出最少需要添加的这种允许关系的个数。

样例输入

1
5
2 4 3 0
4 5 0
0
0
1 0

样例输出

2

模版代码：

 
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
using namespace std;

const int NV = 2005;
const int NE = 5005;

struct Tarjan {
    int dfn[NV];
    int low[NV];
    int index, scc, n;
    bool instack[NV];
    int root[NV];

    stack<int> S;
    struct Edge{
        int v , next, w;
        Edge () {}
        Edge (int V, int NEXT, int W) : v(V), next(NEXT), w(W){}
    }E[NE];
    int head[NV], size;

    inline void init (int nn) {
        n = nn, size = 0;
        memset(head, -1, sizeof(int) * (n + 1));
    }

    inline void insert (int u , int v, int w = 1) {
        E[size] = Edge(v, head[u], w);
        head[u] = size++;
    }

    void tarjan (int i) {
        dfn[i] = low[i] = ++index;
        instack[i] = true;
        S.push(i);
        for (int k = head[i]; k != -1; k = E[k].next) {
            int v = E[k].v;
            if (!dfn[v]) {
                tarjan(v);
                if(low[v] < low[i]) low[i] = low[v];
            } else if (instack[v] && dfn[v] < low[i])
                low[i] = dfn[v];
        }
        if (dfn[i] == low[i]) {
            scc++;
            int x;
            do{
                x = S.top();
                S.pop();
                instack[x] = false;
                root[x] = scc;
            }while (x != i);
        }
    }

    void Solve(){
        while (!S.empty()) S.pop();
        memset(dfn,0,sizeof(dfn));
        index = scc = 0;
        for (int i = 1; i <= n; i++) {
            if(!dfn[i]) tarjan(i);
        }
    }

    struct Relation {
        int u,v;
    }re[NE];
}G;

int main() {
    int n, m, in[NV], out[NV],i;
    int cas;
    scanf("%d",&cas);
    while(cas--) {
        scanf("%d", &n);
        G.init(n);
        int x,k=0;
        for(i=1;i<=n;i++)
        {
            while(scanf("%d",&x)&&x)
            {
                G.insert(i,x);
                G.re[k].u=i;
                G.re[k].v=x;
                k++;
            }
        }

        G.Solve();
        if (G.scc == 1)
        {
            puts("0");
            continue;
        }
        for (int i = 1; i <= G.scc; i++) {
            in[i] = out[i] = 0;
        }
        for (int i = 0; i <k; i++) {
            if (G.root[G.re[i].u] == G.root[G.re[i].v]) continue;
            in[ G.root[ G.re[i].v] ]++;
            out[ G.root[G.re[i].u] ]++;
        }
        int cnt_in = 0 , cnt_out = 0;
        for (int i = 1; i <= G.scc; i++ ) {
            if (in[i] == 0) cnt_in++;
            if (out[i] == 0) cnt_out++;
        }
        printf("%d\n", max(cnt_in,cnt_out));
    }
    return 0;
}
                

ac代码：

 
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<algorithm>
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))

const int nv = 110;
const int ne = 5055;

int low[nv],dfn[nv],head[nv],root[nv],instack[nv];
int in[nv],out[nv];
int size,n,scc,inde;
stack<int>s;

struct edge
{
    int v,next;
}edges[ne];

struct node
{
    int u,v;
}nodes[ne];

void init()
{
    size=0;
    memset(head,-1,sizeof(head));
}
void insert(int x,int y)
{
    edges[size].v=y;
    edges[size].next=head[x];
    head[x]=size++;
}
void tarjan(int t)
{
    dfn[t]=low[t]=++inde;
    instack[t]=1;
    s.push(t);
    for(int j=head[t];j!=-1;j=edges[j].next)
    {
        int v=edges[j].v;
        if(!dfn[v])
        {
            tarjan(v);
            if(low[v]<low[t]) low[t]=low[v];
        }
        else if(instack[v]&&dfn[v]<low[t])
        {
            low[t]=dfn[v];
        }
    }
    if(dfn[t]==low[t])
    {
        scc++;
        int w;
        do
        {
            w=s.top();
            s.pop();
            instack[w]=0;
            root[w]=scc;
        }while(w!=t);
    }
}
void solve()
{
    while(!s.empty())
    s.pop();
    memset(dfn,0,sizeof(dfn));
    scc=0;inde=0;
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        tarjan(i);
    }
}
int main() {
    int i,cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        init();
        int x,k=0;
        for(i=1;i<=n;i++)
        {
            while(scanf("%d",&x)&&x)
            {
                insert(i,x);
                nodes[k].u=i;
                nodes[k].v=x;
                k++;
            }
        }
        solve();
        if (scc == 1)
        {
            puts("0");
            continue;
        }
        for (i = 1; i <= scc; i++) {
            in[i] = out[i] = 0;
        }
        for (i = 0; i <k; i++)
        {
            if (root[nodes[i].u] == root[nodes[i].v]) continue;
            in[root[nodes[i].v]]++;
            out[root[nodes[i].u]]++;
        }
        int indata = 0 , outdata = 0;
        for (i = 1; i <=scc; i++ )
        {
            if (in[i] == 0) indata++;
            if (out[i] == 0) outdata++;
        }
        printf("%d\n", max(indata,outdata));
    }
    return 0;
}