1. 题目

传送门=￣ω￣=

2. 题解

强联通分量，缩点模板题。
第一个问题的答案是缩点以后入度为 0 的点的个数
第二个问题的答案是缩点以后入度为 0 的点的个数和出度为 0 的点的个数中较大的那个
如果只有 1 个强联通分量，那么第二问答案为 0，需要特判

至于证明的话，可以看这个，我懒得写了：

—给定一个有向图，求：

1) 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点

2) 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点

— 顶点数<= 100 解题思路： 1. 求出所有强连通分量 2. 每个强连通分量缩成一点，则形成一个有向无环图 DAG。 3. DAG 上面有多少个入度为 0 的顶点，问题 1 的答案就是多少 在 DAG 上要加几条边，才能使得 DAG 变成强连通的，问题 2 的答案就是多少 加边的方法： 要为每个入度为 0 的点添加入边，为每个出度为 0 的点添加出边 假定有 n 个入度为 0 的点，m 个出度为 0 的点，如何加边？ 把所有入度为 0 的点编号 0,1,2,3,4 ….N -1 每次为一个编号为 i 的入度 0 点可达的出度 0 点，添加一条出边，连到编号为 (i+1)%N 的那个出度 0 点, 这需要加 n 条边 若 m <= n，则 加了这n条边后，已经没有入度0点，则问题解决，一共加了n条边 若 m > n，则还有 m-n 个入度 0 点，则从这些点以外任取一点，和这些点都连上边，即可，这还需加 m-n 条边。
所以，max(m,n) 就是第二个问题的解
此外：当只有一个强连通分支的时候，就是缩点后只有一个点，虽然入度出度为 0 的都有一个，但是实际上不需要增加清单的项了，所以答案是 1，0；

代码（kosaraju）：

#include <cstdio>
#include <cctype>
#include <cstring>
#include <stack>
using namespace std;
template<typename _Tp>void IN(_Tp&dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,head[2][105],nxt[2][10005],to[2][10005],size[2],cnt,pos[105],ans1,ans2;
bool book[105],book2[105];
stack<int> st;
void push(int g,int a,int b)
{
    to[g][size[g]]=b,nxt[g][size[g]]=head[g][a],head[g][a]=size[g]++;
}
void init(int u)
{
    book[u]=1;
    for(int i=head[0][u];i!=-1;i=nxt[0][i])if(!book[to[0][i]])init(to[0][i]);
    st.push(u);
}
void dfs(int u)
{
    book[u]=1,pos[u]=cnt;
    for(int i=head[1][u];i!=-1;i=nxt[1][i])if(!book[to[1][i]])dfs(to[1][i]);
}
int main()
{
    IN(n),memset(head,-1,sizeof(head));
    for(int i=1,j;i<=n;i++)while(IN(j),j)push(0,i,j),push(1,j,i);
    for(int i=1;i<=n;i++)if(!book[i])init(i);
    memset(book,0,sizeof(book));
    while(!st.empty())
    {
        int u=st.top();st.pop();
        if(!book[u])cnt++,dfs(u);
    }
    if(cnt==1){printf("1\n0\n");return 0;}
    memset(book,0,sizeof(book));
    for(int i=1;i<=n;i++)
        for(int j=head[0][i];j!=-1;j=nxt[0][j])
            if(pos[to[0][j]]!=pos[i])
                book[pos[to[0][j]]]=1,book2[pos[i]]=1;
    for(int i=1;i<=cnt;i++){if(!book[i])ans1++;if(!book2[i])ans2++;}
    printf("%d\n%d\n",ans1,max(ans1,ans2));
    return 0;
}