Tarjan全WA求助
查看原帖
Tarjan全WA求助
342868
qfpjm楼主2021/8/9 08:53
#include <bits/stdc++.h>

using namespace std;

struct edge
{
	int u, v;
};

int n, m, dfn[100005], low[100005], cnt, cnt2;
bool in[100005];
vector<edge> G[100005];
vector<int> ans[100005];
stack<int> s;

void Tarjan(int u)
{
	cnt ++;
	low[u] = cnt;
	dfn[u] = cnt;
	in[u] = true;
	s.push(u);
	for (int i = 0 ; i < G[u].size() ; i ++)
	{
		int v = G[u][i].v;
		if (!dfn[v])
		{
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in[v])
		{
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u])
	{
		cnt2 ++;
		int node = 0;
		do
		{
			node = s.top();
			s.pop();
			in[node] = false;
			ans[cnt2].push_back(node);
		}while (node != u);
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1 ; i <= m ; i ++)
	{
		int x, y;
		cin >> x >> y;
		G[x].push_back({x, y});
	}
	Tarjan(1);
	for (int i = 1 ; i <= cnt2 ; i ++)
	{
		sort(ans[i].begin(), ans[i].end());
	}
	cout << cnt2 << endl;
	for (int i = cnt / 2 ; i >= 1 ; i --)
	{
		for (int j = 0 ; j < ans[i].size() ; j ++)
		{
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

2021/8/9 08:53
加载中...