关于Tarjan算法
  • 板块学术版
  • 楼主charleshe
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/2/5 15:58
  • 上次更新2023/10/24 01:37:31
查看原帖
关于Tarjan算法
477258
charleshe楼主2023/2/5 15:58

RT,这是我P2863的AC代码:

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int n,m,u0,v0,ans;
vector<int> v[10001];
stack<int> stk;
int dfn[10001];
int low[10001];
int tim;
int fir[10001];
int sz[10001];
bool vis[10001];
void Tarjan(int x){
	dfn[x]=low[x]=++tim;
	vis[x]=1;
	stk.push(x);
	for(auto y:v[x]){
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(vis[y]) low[x]=min(low[x],low[y]);//重点
		else continue;
	}
	if(dfn[x]==low[x]){
		while(!stk.empty()){
			int t=stk.top();stk.pop();
			vis[t]=0;
			fir[t]=x;
			sz[x]++;
			if(t==x) break;
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u0>>v0;
		v[u0].push_back(v0);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);
	for(int i=1;i<=n;i++){
		if(fir[i]==i&&sz[i]>1) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

显然在重点行我把 dfn 打成 low 了,但这种写法能过。

另外,除此之外,P2341,P2002,P2194我也用相同的方式过了。

请问这么写也是对的吗?还是数据过弱或是很难卡掉?

2023/2/5 15:58
加载中...