64pts 的 tarjan,求调
查看原帖
64pts 的 tarjan,求调
481621
Zhang_Wenjie楼主2023/8/18 09:47
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 5e4 + 10;
struct edge
{
	int to, next;
}e[M];
int top, h[N];
int n, m, dfn[N], low[N], t = 1, ans;
bool in[N];
stack<int> s;

void add(int x, int y)
{
	e[++top] = {y, h[x]};
	h[x] = top;
}

void tarjan(int x)
{
	dfn[x] = low[x] = t ++;
	s.push(x);
	in[x] = true;
	for (int i = h[x]; i ; i = e[i].next)
	{
		int y = e[i].to;
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (in[y])
			low[x] = min(low[x], dfn[y]);
	}
	if (dfn[x] == low[x])
	{
		int cnt = 0;
		while (s.top() != x)
		{
			in[s.top()] = false;
			s.pop();
			cnt ++;
		}
		if (cnt > 1) ans ++;
	}
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1, x, y; i <= m; i ++)
	{
		cin >> x >> y;
		add(x, y);
	}
	for (int i = 1; i <= n; i ++)
		if (!dfn[i]) tarjan(i);
	cout << ans;
		
	return 0;
}
2023/8/18 09:47
加载中...