蓝桥杯2017年第八届真题-发现环 （C++代码）tarjan

        给的是无向边

参考代码:

#ifndef LOCAL
	#include <bits/stdc++.h>
	#define auto int
	#define	constexpr const
#endif
constexpr auto Inf = 0X3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) != '(' && o != ')'); return o;
	}
}
using namespace IO;

const int SIZE = 1E5 + 7;
vector<int> G[SIZE];
int stacks[SIZE], top, scc_index, scc[SIZE], on_stack[SIZE], dfn[SIZE], low[SIZE], dfn_idnex, ans_scc;

void tarjan(int u, int f) {
	on_stack[u] = 1, stacks[++top] = u, dfn[u] = low[u] = ++dfn_idnex;
	for (int v = 0; v < G[u].size(); v++) {
		int e = G[u][v];
		if (e == f) continue;
		if (!dfn[e])
			tarjan(e, u), low[u] = min(low[u], low[e]);
		else if (on_stack[e])
			low[u] = min(low[u], dfn[e]);
	}
	if (dfn[u] == low[u]) {
		scc_index++; int f = 0;
		while (stacks[top] != u) scc[stacks[top]] = scc_index, on_stack[stacks[top--]] = 0, f = 1;
		scc[stacks[top]] = scc_index, on_stack[stacks[top--]] = 0;
		if (f) ans_scc = scc_index;
	}
}

vector<int> vec;

int main() {
	int N = read();
	for (int pos = 1, from, to; pos <= N; pos++)
		from = read(), to = read(), G[from].push_back(to), G[to].push_back(from);
	for (int pos = 1; pos <= N; pos++)
		if (!dfn[pos]) tarjan(pos, 0);
	for (int pos = 1; pos <= N; pos++)
		if (scc[pos] == ans_scc) vec.push_back(pos);
	sort(vec.begin(), vec.end());
	for (int pos = 0; pos < vec.size(); pos++)
		printf("%d ", vec[pos]);
}