一道tarjan的模板水题
在这里还是着重解释一下tarjan的代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int cnt;//记录强联通分量的个数
int visitnum;//遍历的步数
int dfn[100010];//记录元素第一次被访问的步数
int low[100010];//包含i的强联通分量最早被访问的步数
int num[100010];//记录强联通分量里的点的个数
int belong[100010];//i从属的强联通分量的序号
int top;//栈中元素的个数
int stack[100010];//手打栈
int instack[100010];//判断元素是否在栈中
int head[100010];
struct node{
int to,next;
}edge[100010];//链式前向星存边
int read()//读入优化
{
int x=0,w=1;char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}
while(ch<='9'&&ch>='0') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;
}
void tarjan(int);
int main()
{
int ans=0;
int p,q;
n=read();m=read();
for(int i=1;i<=m;i++)
{
p=read();q=read();
edge[i].to=q;
edge[i].next=head[p];
head[p]=i;
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])//i没被访问过了
{
tarjan(i);
}
}
for(int i=1;i<=cnt;i++)
{
if(num[i]>1)
ans++;
}
printf("%d",ans);
}
void tarjan(int u)
{
int v;
visitnum++;
dfn[u]=low[u]=visitnum;
stack[++top]=u;//入栈
instack[u]=1;//入栈
for(int i=head[u];i;i=edge[i].next)
{
v=edge[i].to;
if(!dfn[v])//还没被访问过
{
tarjan(v);
low[u]=min(low[u],low[v]);//判断u是否为v的子节点
}
else if(instack[v])
{
low[u]=min(low[u],dfn[v]);
//其实这里的dfn[v]也能换成low[v] 但最好写dfn
}
}
if(dfn[u]==low[u])//u为强联通分量的根
{
cnt++;
do//退栈
{
num[cnt]++;
v=stack[top--];
belong[v]=cnt;
instack[v]=0;
}while(u!=v);
}
}