【题意】
见:http://blog.csdn.net/ascii991/article/details/7466278
【思路】
缩点+tarjan,思路也可以到上面的博客去看。(吐槽:这道题其实我没有AC。我过了当年IOI的数据,而把别人AC掉的程序带进去,明显过不了IOI的数据!求POJ修正一下!)我在这里引用一下:
【错误点】
1.tarjan要进行多次,详见程序注释
2.循环从0开始还是从1开始要看清楚!
3.但只有一个连通分量的时候,不需要再增加边!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
using namespace std;
const int MAXN=+;
int n;//学校的总数
int u[MAXN],v[MAXN];//记录每一条边的起始点和终点
int sp[MAXN];//记录缩点之后每个点对应的编号
int tot=;//有向图中边的总数
int vis[MAXN];
int instack[MAXN];
int dfn[MAXN],low[MAXN];
int indegree[MAXN],outdegree[MAXN];//记录缩点后的每一个点的入度与出度
vector<int> E[MAXN];
stack<int> S;
int T=;
int cnt=;//为缩点后的每一个点编号 void tarjan(int u)
{
dfn[u]=low[u]=++T;
vis[u]=;
S.push(u);
instack[u]=; for (int i=;i<E[u].size();i++)
{
int son=E[u][i];
if (!vis[son])
{
tarjan(son);
low[u]=min(low[son],low[u]);
}
else
if (vis[son] && instack[son])
low[u]=min(dfn[son],low[u]);
} if (dfn[u]==low[u])
{
cnt++;
int x;
do
{
x=S.top();
S.pop();
sp[x]=cnt;
instack[x]=;
}while (x!=u);
}
} void init()
{
memset(vis,,sizeof(vis));
memset(instack,,sizeof(instack));
scanf("%d",&n);
for (int i=;i<=n;i++)
{
int to;
while (scanf("%d",&to) && to)
{
tot++;
u[tot]=i;v[tot]=to;
E[i].push_back(to);
}
}
} void find()
{
memset(indegree,,sizeof(indegree));
memset(outdegree,,sizeof(outdegree));
if (cnt>)
{
for (int i=;i<=tot;i++)
/*错误点:写成了i=0;i<tot,导致有时候没有进入循环!*/
{
if (sp[u[i]]!=sp[v[i]])
{
outdegree[sp[u[i]]]++;
indegree[sp[v[i]]]++;
}//找出缩点后各点的出度和入度
} int noin=,noout=;
for (int i=;i<=cnt;i++)
{
if (indegree[i]==) noin++;
if (outdegree[i]==) noout++;
}
cout<<noin<<endl;
cout<<max(noin,noout)<<endl;
}
else if (cnt==) printf("1\n\0\n");
} int main()
{
init();
for (int i=;i<=n;i++) if (vis[i]==) tarjan(i);
/*错误点:一开始直接tarjan(1)了,导致有一些学校没有被访问到!每次随机从没有访问的某个结点开始!*/
find();
return ;
}