/*
强连通分量内的点可以互相传送，可以直接缩点
缩点后得到一棵树
第一问的答案是零入度点数量，
第二问： 加多少边后变成强连通图
树上入度为0的点有p个，出度为0的点为q，那么答案就是max(p,q)
如果缩点后是一个点，答案就是0
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define maxn 105
struct Edge{
int to,nxt;}edge[
100005<<
1];
int n,head[maxn],tot;
void addedge(
int u,
int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++
;
}
int dfn[maxn],low[maxn],stack[maxn],ins[maxn],c[maxn],cnt,top,ind;
void tarjan(
int x){
low[x]=dfn[x]=++
ind;
stack[++top]=
x;
ins[x]=
1;
for(
int i=head[x];i!=-
1;i=
edge[i].nxt){
int y=
edge[i].to;
if(!
dfn[y]){
tarjan(y);
low[x]=
min(low[x],low[y]);
}
else if(ins[y])
low[x]=
min(low[x],low[y]);
}
if(dfn[x]==
low[x]){
cnt++
;
int y;
do{
y=stack[top--
];
ins[y]=
0;
c[y]=
cnt;
}while(y!=
x);
}
}
void init(){
cnt=tot=ind=top=
0;
memset(dfn,0,
sizeof dfn);
memset(low,0,
sizeof low);
memset(stack,0,
sizeof stack);
memset(ins,0,
sizeof ins);
memset(c,0,
sizeof c);
memset(head,-
1,
sizeof head);
}
int main(){
while(cin>>
n){
init();
for(
int i=
1;i<=n;i++
){
int u=
i,v;
while(scanf(
"%d",&
v),v)
addedge(u,v);
}
for(
int i=
1;i<=n;i++
)
if(!
dfn[i])
tarjan(i);
if(cnt==
1){
printf("1\n0\n");
continue;
}
//缩点
int in[maxn]={},
out[maxn]={},p=
0,q=
0;
for(
int x=
1;x<=n;x++
)
for(
int i=head[x];i!=-
1;i=
edge[i].nxt){
int y=
edge[i].to;
if(c[x]==c[y])
continue;
in[c[y]]++;
out[c[x]]++
;
}
for(
int i=
1;i<=cnt;i++
){
if(
in[i]==
0)p++
;
if(
out[i]==
0)q++
;
}
printf("%d\n%d\n",p,max(p,q));
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10463271.html
