题目大意

N(2

思路

用tarjan求强连通分量后求每一个的出度和入度即可

#include 
#include 
#include 
#include 
using namespace std;
#define fill(x, y) sizeof(x, y, sizeof(x))
#define maxn 101
int n;
struct edge
{
    int from, to, next;
}e[maxn*50];
int ls[maxn*50], dfn[maxn], low[maxn], belong[maxn], in[maxn], out[maxn];
int dindex = 0, bcnt = 0;
bool instack[maxn];
stack s;
void tarjan(int x)
{
    dindex++;
    dfn[x] = dindex;
    low[x] = dindex;
    s.push(x);
    instack[x] = 1;
    for (int i = ls[x]; i; i = e[i].next)
    {
        int to = e[i].to;
        if (dfn[to] == 0)
        {
            tarjan(to);
            if (low[x] > low[to]) low[x] = low[to];
        }
        else
        {
            if (instack[to] && dfn[to] < low[x])
                low[x] = dfn[to];
        }
    }
    if (dfn[x] == low[x])
    {
        bcnt++;
        int j;
        do
        {
            j = s.top();
            instack[j] = 0;
            s.pop();
            belong[j] = bcnt;
        }
        while(x != j);
    }
}
void solve()
{
    while (! s.empty()) s.pop();
    fill(dfn, 0);
    for (int i = 1; i <= n; i++)
        if (dfn[i] == 0) tarjan(i);
}
int main()
{

    while(~scanf("%d", &n))
    {
    int l = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        while (scanf("%d", &x) && x != 0)
        {
            e[++l].from = i;
            e[l].to = x;
            e[l].next = ls[i];
            ls[i] = l;
        } 
    }

    solve();
    for (int i = 1; i <= l; i++)
    {
        if (belong[e[i].from] != belong[e[i].to])
        {
            out[belong[e[i].from]]++;
            in[belong[e[i].to]]++;
        }
    }
    int ans = 0;
    for (int i = 1; i <= bcnt; i++)
        if (in[i] == 0) ans++;
    int ll = 0, rr = 0;
    for (int i = 1; i <= bcnt; i++)
    {
        if (out[i] == 0) ll++;
        if (in[i] == 0) rr++;
    }
    if (bcnt == 1) {printf("1\n0\n"); continue;}
    printf("%d\n", ans);
    printf("%d\n", ll > rr ? ll : rr);
}
}