给我们一个有向图，有两个问题
1、最少要给多少个点发消息，才能使得所有的点都收到消息（消息可以随边传递）
2、最少需要多少条边才能使得图变成强连通图
对于一个强连通分量，可以当做一个点来考虑，所以我们可以缩点，然后得到DAG图，
那么对于第一个问，即是入度为0的点有多少个，因为入度为0的点无法收到消息。
对于第二问，只要加max(s1,s2)条边，就能使得DAG变成强连通图， s1表示入度为0的点的个数，s2表示出度为0的点的个数
设s1 > s2, 那么首先加s2条边，这s2条边连接的是入度为0和出度为0的点，
然后剩下s1-s2个入度为0的点， 那么随便加s1-s2条边即可。
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <iostream>
typedef __int64 LL;
const int INF = << ;
using namespace std;
/*
考虑如果是的一个有向图，变成连通图，
将强联通分量缩成一个点，
然后，如果某一个联通分量和其他的联通分量没有边，那么要加两条边，如果只有一条边
那么只要加1条边
*/
const int N = + ;
int dfn[N], low[N], sccno[N], dfs_clock, cnt;
stack<int> st;
vector<int> g[N]; void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfs_clock;
st.push(u);
for (int i = ; i<g[u].size(); ++i)
{
int v = g[u][i];
if (dfn[v] == )
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if (sccno[v] == )//因为有向图存在横插边，不能用横插边来更新low[u]
{
low[u] = min(low[u], low[v]);
}
}
//同样，因为强连通分量可以分布在根结点的两个分支上，所以在递归返回的时候调用
if (low[u] == dfn[u])
{
cnt++;
for (;;)
{
int x = st.top();
st.pop();
sccno[x] = cnt;
if (x == u)
break;
}
}
}
bool in[N], out[N];
int main()
{ int n;
while (scanf("%d", &n) != EOF)
{
dfs_clock = cnt = ;
while (!st.empty()) st.pop();
for (int i = ;i <= n;++i)
{
sccno[i] = ;
g[i].clear();
low[i] = dfn[i] = ;
in[i] = out[i] = false;
}
for (int i = ;i <= n;++i)
{
int u = i, v;
while (scanf("%d", &v), v)
g[u].push_back(v);
}
for (int i = ;i <= n;++i)
{
if (dfn[i] == )
tarjan(i, -);
}
for (int i = ;i <= n;++i)
{
for (int j = ;j < g[i].size();++j)
{
int v = g[i][j];
if (sccno[i] == sccno[v]) continue;
out[sccno[i]] = true;
in[sccno[v]] = true;
}
}
if (cnt == )
{
printf("1\n0\n");
continue;
}
int cnt1 = , cnt2 = ;
for (int i = ;i <= cnt;++i)
{
if (!in[i]) cnt1++;
if (!out[i]) cnt2++;
}
printf("%d\n", cnt1);
printf("%d\n", max(cnt1, cnt2));
}
return ;
}