基环树找环板子TLE求调/hack
查看原帖
基环树找环板子TLE求调/hack
912180
Anitsoler楼主2024/2/23 17:56

/kel

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
int n, fa[N];

bool vis[N], incir[N];
void findcir(int u) {
	while (!vis[u]) vis[u] = true, u = fa[u];
	int v = u;
	while (true) {
		incir[v] = true;
		v = fa[v];
		if (u == v) break;
	}
}

int main() {
	cin >> n;
	for (int i = 1, u, v; i <= n; i++) {
		cin >> u >> v;
		fa[v] = u;
	}
	for (int u = 1; u <= n; u++)
		if (!vis[u])
			findcir(u);
	for (int u = 1; u <= n; u++) 
		if (incir[u])
			cout << u << ' ';
	return 0;
}
2024/2/23 17:56
加载中...