80pts,vis为什么要回溯?
查看原帖
80pts,vis为什么要回溯?
530570
Firrel_qaq楼主2024/1/24 15:05
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
//变量定义区域
//=========================
	//全局遍历
	int n,m;
	//=========================
	//链式前向星
	struct edge{
		int to,nxt;
	}mp[100005];
	int tot;
	int head[100005];
	//=========================
	//tarjan
	int low[100005],dfn[100005];
	int stac[100005],vis[100005];
	int top,id,cnt;
//=========================
//函数定义区域
//=========================
	//链式前向星添加边
void add(int u,int v){
	mp[++tot].to = v;
	mp[tot].nxt = head[u];
	head[u] = tot;
	return ;
}
//=========================
	//tarjan函数本体
void tarjan(int x,int fa){
	//cout << x << endl;
	low[x] = dfn[x] = ++id;
	stac[++top] = x;
	for(int i = head[x];i;i = mp[i].nxt){
		int y = mp[i].to;
		if(!dfn[y]){
			tarjan(y,x);
			low[x] = min(low[x],low[y]);
			if(low[x] == dfn[x]){
				int t = 0,cou = 0;
				while(t != x){
					if(top <= 0) break;
					t = stac[top--];
					cou++;
				}
				if(top) top--;
				if(cou > 1) cnt++;
			}
		}
		else low[x] = min(low[x],dfn[y]);
	}
	return ;
}
int main(){
	//输入与建图
	//-------------------------------------
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		if(u == v) continue;
		add(u,v);
	}
	//tarjan判断是否成环
	//-------------------------------------
	for(int i = 1;i <= n;i++){
		if(!dfn[i]){
			if(head[i] == 0) continue;
			tarjan(i,0);
		}
	}
	if(cnt) printf("%d",cnt);
	else printf("1");
	return 0;
}

2024/1/24 15:05
加载中...