Tarjan 模板题
第一问就是缩点之后看有多少个入度为零的点就好了。
第二问是在缩点后将每个点的入度和出度都求出（只要有入度或出度就置为1），然后比较哪个有值的多，将多的作为答案输出。原因是由题可得，要使缩完的点也构成一个强连通分
量，即入度和出度都大于等于1。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 10010
using namespace std;
inline int read()
{
int x=;
bool f=;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=;
for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
if(f) return x;
return -x;
}
inline void write(int x)
{
if(x<){putchar('-');x=-x;}
if(x>)write(x/);
putchar(x%+'');
}
struct node
{
int v,nex;
}edge[maxn];
int n,cnt,inl,top,res1,res2,num,cd2,rd2;
int head[maxn],st[maxn],low[maxn],dfn[maxn],inn[maxn],si[maxn],rd[maxn],cd[maxn];
inline void add(int x,int y)
{
cnt++;
edge[cnt].v=y;
edge[cnt].nex=head[x];
head[x]=cnt;
}
inline void Tarjan(int from)
{
dfn[from]=low[from]=++num;
st[++top]=from;
for(int i=head[from];i!=-;i=edge[i].nex)
{
int to=edge[i].v;
if(!dfn[to])
{
Tarjan(to);
low[from]=min(low[from],low[to]);
}
else if(!inn[to])
low[from]=min(low[from],dfn[to]);
}
if(low[from]==dfn[from])
{
inn[from]=++inl;
++si[inl];
while(st[top]!=from)
{
++si[inl];
inn[st[top]]=inl;
--top;
}
--top;
}
}
int main()
{
memset(head,-,sizeof(head));
n=read();
for(int i=;i<=n;i++)
{
int x;
while()
{
x=read();
if(x!=)add(i,x);
else break;
}
}
for(int i=;i<=n;i++)
if(!dfn[i])
Tarjan(i);
for(int i=;i<=n;i++)
for(int j=head[i];j!=-;j=edge[j].nex)
{
if(inn[i]!=inn[edge[j].v])
{
rd[inn[edge[j].v]]++;
cd[inn[i]]++;
} }
if(inl==)
{
cout<<<<endl<<;
return ;
}
for(int i=;i<=inl;i++)
if(rd[i]==)
res1++;
write(res1);
cout<<endl;
for(int i=;i<=inl;i++)
{
if(cd[i]==)
cd2++;
if(rd[i]==)
rd2++;
}
res2=max(cd2,rd2);
write(res2);
return ;
}
请各位大佬斧正