社区讨论

初学tarjan板子题求助

P2863[USACO06JAN] The Cow Prom S参与者 13已保存回复 35

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
35 条
当前快照
1 份
快照标识符
@mi7cgz5a
此快照首次捕获于
2025/11/20 19:25
4 个月前
此快照最后确认于
2025/11/20 23:42
4 个月前
查看原帖
CPP
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N=10010;
int n,m,num,sum,color[N];    //  color表示每个强联通分量的个数 
int dfn[N],low[N],ans;
bool vis[N];
vector<int> v[N];
stack<int> s;
void tarjan(int x)   //  当前点 
{
	dfn[x]=low[x]=++num;
	s.push(x);
	vis[x]=true;
	for(int i=0;i<v[x].size();i++)
	{
		int y=v[x][i];
		if(!dfn[y])   // 如果这个点没访问过 
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else low[x]=min(low[x],dfn[y]);   //  访问过
	}
	if(low[x]==dfn[x]) 
	{
		sum++;
		while(s.top()!=x)
		{
			vis[s.top()]=false;
			s.pop();
			color[sum]++; 
		}
	}
}
int main()
{
	cin>>n>>m;
	int a,b;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		v[a].push_back(b);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i);
	for(int i=1;i<=sum;i++) if(color[i]>1) ans++;
	cout<<ans;
	return 0;
}
八十分 不知道哪里挂了

回复

35 条回复,欢迎继续交流。

正在加载回复...