悬赏1关注,tarjan模板题求助
查看原帖
悬赏1关注,tarjan模板题求助
952621
ForMyLove楼主2023/4/17 23:39
#include<iostream>
#include<vector>
#define maxn 10001
#include<stack>
using namespace std;
vector<int>edge[maxn];
stack <int>s;
int low[maxn],dfn[maxn],tot,ins[maxn],siz[maxn],cnt,ans;
int n,m,v,u;
void tarjan(int u){
	low[u]=dfn[u]=++tot;
	s.push(u); ins[u]=1;
	for (int i=0;i<edge[u].size();i++){
//		cout<<u<<"-->"<<v<<endl;
		v=edge[u][i];
		if (!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } 
		else if (ins[v]){ low[u]=min(low[u],dfn[v]); }
	}
	if (low[u]==dfn[u]){
		int y; cnt++;
		do {
			y=s.top();s.pop();
			siz[cnt]++,ins[y]=0;
		}
		while (u!=y);
//		cnt++;
//		while (s.top()!=u){
//			int t=s.top();
//			s.pop(); ins[u]=0; siz[cnt]++;
//		}
//		s.pop(); ins[u]=0; siz[cnt]++;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>u>>v; edge[u].push_back(v);
	}
//	for (int i=1;i<=n;i++){
//		for (int j:edge[i]){
//			cout<<i<<"-->"<<j<<' '; 
//		}
//		cout<<endl;
//	}
	for (int i=1;i<=n;i++){
		if (!dfn[i]) tarjan(i);
	}
	for (int i=1;i<=cnt;i++){
		if (siz[i]>1) ans++;
	}
	cout<<ans;
	return 0;
}

明天过来看,谢谢

2023/4/17 23:39
加载中...