POJ_1236
这个题目的TaskA实际上就是在求入度为0的强连通分量的个数，而TaskB实际上就是在求各个强连通分量中入度为0的个数与出度为0的个数的较大值。
同时这个题目与之前做的点双连通的分量有所不同，其中有一点便是在求强连通分量时对于low[u]>dfn[v]时更新low[u]的值，有一个前提条件就是v在栈内，因而要单独用一个数组标记v是否在栈内，而求点双连通分量时则不需要这个数组，因为只要G[u][v]为1，且dfn[v]不为0，那么v一定在栈中。
对于双连通分量为什么不需要标记v是否在栈内，可以先假设v不在栈中但dfn[v]不为0，而如果G[u][v]为1，那么在dfs的过程中，要么v应该在u的后面被搜到，那么dfn[v]显然应该为0，这样与假设矛盾，或者v应该在u的前面被搜到，那么由于u在v后面，v出栈之前必定u已经出栈了，而现在u又确实在栈里，这也是矛盾的(因为出栈后的元素不会再进栈)，所以对于求点双连通分量的过程，如果在dfs过程中出现了G[u][v]为1且dfn[v]不等于0的情况，那么v一定在栈中。
#include<stdio.h>
#include<string.h>
int ans[110][110],indgr[110],outdgr[110],G[110][110];
int ins[110],s[110],top,num,N,dfn[110],low[110],time;
void tarjan(int u)
{
int i,v;
dfn[u]=low[u]=++time;
s[top++]=u;
ins[u]=1;
for(v=0;v<N;v++)
if(G[u][v])
{
if(!dfn[v])
{
tarjan(v);
if(low[v]<low[u])
low[u]=low[v];
}
elseif(ins[v]&&dfn[v]<low[u])
low[u]=dfn[v];
}
if(dfn[u]==low[u])
{
s[top]=-1;
for(i=0;s[top]!=u;i++)
{
ans[num][i]=s[--top];
ins[ans[num][i]]=0;
}
num++;
}
}
int main()
{
int i,j,k,taskB,p,q,taskA,ok,u;
while(scanf("%d",&N)==1)
{
for(i=0;i<N;i++)
while(1)
{
scanf("%d",&j);
if(j==0)
break;
j--;
G[i][j]=1;
}
memset(ans,-1,sizeof(ans));
memset(ins,0,sizeof(ins));
memset(dfn,0,sizeof(dfn));
time=num=top=0;
for(u=0;u<N;u++)
if(!dfn[u])
tarjan(u);
if(num==1)
{
printf("1\n0\n");
continue;
}
memset(indgr,0,sizeof(indgr));
memset(outdgr,0,sizeof(outdgr));
for(i=0;i<num;i++)
for(j=0;j<num;j++)
{
if(i==j)
continue;
ok=0;
for(p=0;ans[i][p]!=-1;p++)
{
for(q=0;ans[j][q]!=-1;q++)
if(G[ans[i][p]][ans[j][q]])
{
indgr[j]++;
outdgr[i]++;
ok=1;
break;
}
if(ok)
break;
}
}
taskB=taskA=0;
for(i=0;i<num;i++)
{
if(indgr[i]==0)
taskA++;
if(outdgr[i]==0)
taskB++;
}
taskB=taskB>taskA?taskB:taskA;
printf("%d\n%d\n",taskA,taskB);
}
return0;
}