萌新刚学OI,求助tarjan板子
查看原帖
萌新刚学OI,求助tarjan板子
298549
SIXIANG32楼主2020/7/9 18:14

RT
照着日报打的,打错了/kk
求大佬修改

#include<iostream>
#include<vector>
#define root 1
using namespace std;
int dfn[10010],low[10010],cnt=0,cl=0,stack[10010],top; 
int color[10010];//染色数组 
int num[10010];//大小 
bool vis[10010];//是否入了栈
inline int min(int x,int y){return ((x<y)?(x):(y));}; 
vector<int>gra[10010];
inline void tarjan(int u)
{
	dfn[u]=low[u]=++cnt;
	stack[top++]=u,vis[u]=1;
	for(int p=0;p<gra[u].size();p++)
	{
		if(!dfn[gra[u][p]])
		{
			tarjan(dfn[gra[u][p]]);
			low[gra[u][p]]=min(low[gra[u][p]],low[u]);
		}
		else
			if(!vis[gra[u][p]])
				low[gra[u][p]]=min(low[gra[u][p]],low[u]);
	}
	if(dfn[u]==low[u])
	{
		vis[u]=0,color[u]=++cl;
		while(stack[top]!=u)
		{
			num[cl]++;
			color[stack[top]]=cl;
			vis[stack[top--]]=0;
		}
		top--;
	}
}
int main()
{
	int n,m,ans=0;
	cin>>n>>m;
	for(int p=1,x,y;p<=m;p++)
		cin>>x>>y,gra[x].push_back(y);
	tarjan(root);
	for(int p=1;p<=n;p++)
		if(!dfn[p])
			tarjan(p);
	for(int p=1;p<=n;p++)
		if(num[p]>1)
			ans++;
	cout<<ans<<endl;
}
2020/7/9 18:14
加载中...