52分求调(玄关)
查看原帖
52分求调(玄关)
810054
suzichen03楼主2024/5/18 11:49
#include<iostream>
#include<vector>
#include<stack>
#include<cmath>
using namespace std;
struct Edge
{
	int from,to;
};
vector<Edge> g[10001];
int dfn[10001],low[10001];
stack<int> st;
bool ins[10001];
int cnt;
void tarjan(int u)
{
	dfn[u]=low[u]=++cnt;
	ins[u]=1;
	st.push(u);
	for(auto t:g[u])
	{
		if(dfn[t.to]==0)
		{
			tarjan(t.to);
			low[u]=min(low[u],low[t.to]);
		}
		else if(ins[t.to]==1)
		{
			low[u]=min(low[u],dfn[t.to]);
		}
	}
	if(low[u]==dfn[u])
	{
		while(st.top()!=u)
		{
			ins[st.top()]=0;
			st.pop();
		}
		ins[u]=0;
		st.pop();
	}
	return ;
}
int ans;
int sum[10001];
int main()
{
	int n,m;
	cin >> n >> m;
	int u,v;
	for(int i=1;i<=m;i++)
	{
		cin >> u >> v;
		g[u].push_back({u,v});
	}
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0)
		{
			tarjan(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		sum[low[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(sum[i]>1)
		{
			ans++;
		}
	}
	cout << ans << '\n';
	return 0;
}
2024/5/18 11:49
加载中...