P2746 [USACO5.3]校园网Network of Schools

任务一：求缩完点后入度为0的点的个数（有向边）

任务二：求缩完点后入度为0和出度为0的最大值（要把图构造成强连通分量）

注意，任务二需要特判整张图是一个强联通

#include
#include
#include
#include
using namespace std;
const int maxn=;
int pre[maxn],other[maxn],last[maxn],l;
int n;
void add(int x,int y)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
}
int dfn[maxn],low[maxn];
int cnt;
int belong[maxn],qw;
int ru[maxn];
stack s;
void dfs(int x)
{
low[x]=dfn[x]=++cnt;
s.push(x);
//ru[x]=1;
for(int p=last[x];p;p=pre[p])
{
int v=other[p];
// if(v==fa) continue;
if(!dfn[v])
{
dfs(v);
low[x]=min(low[x],low[v]);
}
else if(!belong[v])
{
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x])
{
belong[x]=++qw;
while()
{
int y=s.top();
s.pop();
//ru[y]=0;
belong[y]=qw;
if(y==x) break;
}
}
}
int ans1,ans2;
int chu[maxn];
int main()
{
scanf("%d",&n);
for(int i=,x;i<=n;i++) while(scanf("%d",&x)&&x){add(i,x);}
for(int i=;i<=n;i++)
{
if(!dfn[i])
{
dfs(i);
}
}
for(int i=;i<=n;i++)
{
for(int p=last[i];p;p=pre[p])
{
int v=other[p];
if(belong[i]!=belong[v])
{
chu[belong[i]]++;
ru[belong[v]]++;
}
}
}
for(int i=;i<=qw;i++)
{
if(!ru[i]) ans1++;
if(!chu[i]) ans2++;
}
if(qw==)
{
printf("1\n0");
return ;
}
printf("%d\n",ans1);
printf("%d",max(ans1,ans2));
return ;
}