题目链接
#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
int low[maxn],dfn[maxn];
int nxt[maxn],ru[maxn],cu[maxn],head[maxn],to[maxn];
int n,m;
int stk[maxn],co[maxn];
int tol=0,cnt=0,dfst=0,top=0,col=0;
void add(int x,int y)
{to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;
}
void tarjan(int x)
{dfn[x]=low[x]=++dfst;stk[++top]=x;//入栈 for(int i=head[x];i!=-1;i=nxt[i]){int v=to[i];if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}else if(!co[v])low[x]=min(low[x],dfn[v]);}if(dfn[x]==low[x]){co[x]=++col;//强连通栈 while(stk[top]!=x){co[stk[top]]=col;--top;}--top;}
}
int main()
{scanf("%d",&n);memset(head,-1,sizeof head);for(int i=1;i<=n;i++){int x;while(~scanf("%d",&x)&&x){add(i,x);}}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=n;i++)for(int j=head[i];j!=-1;j=nxt[j]){if(co[i]==co[to[j]])continue;ru[co[to[j]]]++;cu[co[i]]++;}int ans1=0,ans2=0;for(int i=1;i<=col;i++){if(ru[i]==0)ans1++;if(cu[i]==0)ans2++;}if(col==1)printf("%d\n0\n",ans1);elseprintf("%d\n%d\n",ans1,max(ans1,ans2));return 0;}```