题意：一张有向图，一问至少给几个点发送软件，才能让所有点都能收到软件；二问是至少添加几条边才能让整个图是一个连通分量；
分析：一般求连通分量都会求缩点，在这里缩点之后，生成一张新的图，在新的图中求每一个点的出度，入度。答案就是sum(入度=0)，max（sum（出度 == 0）,sum（入度 == 0））;
注意：如果整张图本来就是一个强连通分量，需要特判。因为它出度，入度都等于0，即max(1,1) = 1，但是实际上不用再补充边了，应该是0，按照上面的分析答案就错了。
///POJ1236
///时间复杂度也是O(N+M)
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <iostream>
#define repu(i,a,b) for(int i=a;i<b;i++)
using namespace std;
#define N 105 /// 题目中可能的最大点数
stack<int>sta; /// 存储已遍历的结点
vector<int>gra[N]; /// 邻接表表示图
int dfn[N]; /// 深度优先搜索访问次序
int low[N]; /// 能追溯到的最早的次序
int InStack[N];
/// 检查是否在栈中(2：在栈中，1：已访问，且不在栈中，0：不在)
vector<int> Component[N]; /// 获得强连通分量结果
int InComponent[N]; /// 记录每个点在第几号强连通分量里
int Index,ComponentNumber;/// 索引号，强连通分量个数
int n, m; /// 点数，边数
int d[N][N],chu[N],ru[N]; void init()///清空容器，数组
{
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
memset(chu, , sizeof(chu));
memset(ru, , sizeof(ru));
memset(InStack, , sizeof(InStack));
Index = ComponentNumber = ;
for (int i = ; i <= n; ++ i)
{
gra[i].clear();
Component[i].clear();
}
repu(i,,n+)
repu(j,,n+)
d[i][j] = ;
while(!sta.empty())
sta.pop();
}
void tarjan(int u)
{
InStack[u] = ;
low[u] = dfn[u] = ++ Index;
sta.push(u);///寻找u所在的强连通分量
for (int i = ; i < gra[u].size(); ++ i)
{
int t = gra[u][i];
if (dfn[t] == )///不在的继续递归
{
tarjan(t);///递归到头了就
low[u] = min(low[u], low[t]);
}
else if (InStack[t] == )///在栈里
{
low[u] = min(low[u], dfn[t]);
}
}
if(low[u] == dfn[u])///sta出栈就是一个强连通分量的
{
++ComponentNumber;///强连通分量个数
while (!sta.empty())
{
int j = sta.top();
sta.pop();
InStack[j] = ;///已访问但不在栈中
Component[ComponentNumber].push_back(j);
///用vector存储第ComponentNumber个强连通分量
InComponent[j]=ComponentNumber;
///记录每个点在第几号强连通分量里
if (j == u)
break;
}
}
}
void input()
{
repu(i,,n+)
{
while(scanf("%d",&m) &&m)
d[i][m] = ,gra[i].push_back(m);///有向图才有强连通分量
}
} void solve(void)
{
for(int i=; i<=n; i++)
if(!dfn[i])
tarjan(i);
if(ComponentNumber == )
{
printf("1\n0\n");
return;
}
///缩点
for(int i=; i<=ComponentNumber; i++)
{
for(int j = ; j < Component[i].size(); j++)
{
for(int k = ; k<=n; k++)
{
if(d[k][Component[i][j]] && k != Component[i][j])
{
int s = InComponent[k];
int t = InComponent[Component[i][j]];
if(s!=t)
{
chu[s]++;
ru[t]++;
}
}
}
}
}
int sum = ,num = ;
for(int i=; i<=ComponentNumber; i++)
{
if(!chu[i])
sum++;
if(!ru[i])
num++;
}
printf("%d\n%d\n",num,max(sum,num));
} int main()
{
while(~scanf("%d",&n))
{
init();
input();
solve();
/*每一个强连通分量的具体数字
for(int i = 1; i <= ComponentNumber; i++)
{
for(int j = 0; j < Component[i].size(); j++)
if(!j)
cout << Component[i][j];
else
cout <<"-->"<< Component[i][j];
cout<<endl;
}
*/
}
return ;
}