Codeforces Round 923 (Div. 3) F题 Microcycle（生成树，并查集，DFS）

题目链接

Codeforces Round 923 (Div. 3) F题 Microcycle

思路

在kruskal求最小生成树的过程中，若当前边所连的两个点在并查集中处于同一个集合，则连上当前边就会产生环。

因此我们可以用kruskal求一遍最大生成树，最后一个出现上述情况的边，即为答案。

找出答案边之后，我们只需要使用dfs搜一遍这个图便可以找到该边所在的环。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, m, End, tot;
int ans[N];
bool st[N];
vector<int>mp[N];
struct Edge
{
	int u, v, val;
	bool operator<(const Edge &x) {
		return val > x.val;
	}
};
vector<Edge>edge;
struct DSU {
	std::vector<int> f, siz;

	DSU() {}
	DSU(int n) {
		init(n);
	}

	void init(int n) {
		f.resize(n);
		std::iota(f.begin(), f.end(), 0);
		siz.assign(n, 1);
	}

	int find(int x) {
		while (x != f[x]) {
			x = f[x] = f[f[x]];
		}
		return x;
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	bool merge(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return false;
		}
		siz[x] += siz[y];
		f[y] = x;
		return true;
	}

	int size(int x) {
		return siz[find(x)];
	}
};
bool dfs(int u, int fu)
{
	ans[++tot] = u;
	if (u == End)
	{
		cout << tot << endl;
		for (int i = 1; i <= tot; i++)
		{
			cout << ans[i] << " ";
		}
		cout << endl;
		return true;
	}
	st[u] = true;
	for (int j : mp[u])
	{
		if (j == fu || st[j])
			continue;
		if (dfs(j, u))
			return true;
	}
	tot--;
	return false;
}
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		mp[i].clear();
		st[i] = false;
	}
	tot = 0;
	edge.clear();
	for (int i = 1, u, v, w; i <= m; i++)
	{
		cin >> u >> v >> w;
		edge.push_back({u, v, w});
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	sort(edge.begin(), edge.end());
	DSU dsu(n + 1);
	int idx = 0;
	for (int i = 0; i < edge.size(); i++)
	{
		if (dsu.same(edge[i].u, edge[i].v))
		{
			idx = i;
		}
		else dsu.merge(edge[i].u, edge[i].v);
	}
	cout << edge[idx].val << " ";
	int u = edge[idx].u, v = edge[idx].v;
	End = u;
	dfs(v, u);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}