Codeforces Round 923 (Div. 3) F. Microcycle【Kruskal算法思想+并查集+dfs找环】

本文主要是介绍Codeforces Round 923 (Div. 3) F. Microcycle【Kruskal算法思想+并查集+dfs找环】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://codeforces.com/problemset/problem/1927/F

题意翻译

给定一张 n 个点，m 条边，边有边权的无向图，无重边自环，不保证连通。定义一个简单环为不经过重复点与重复边的环路径，保证全图至少有一个简单环。记一个简单环的权值是环上最小的边权，你需要找到任意一个全图中权值最小的一个简单环并输出它。

输入输出描述：

3≤n,m≤2×10^5,w≤10^6。

输入输出样例
输入 
5
6 6
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
6 6
1 2 10
2 3 8
3 1 5
4 5 100
5 6 40
6 4 3
6 15
1 2 4
5 2 8
6 1 7
6 3 10
6 5 1
3 2 8
4 3 4
5 3 6
2 6 6
5 4 5
4 1 3
6 4 5
4 2 1
3 1 7
1 5 5
4 6
2 3 2
1 3 10
1 4 1
3 4 7
2 4 5
1 2 2
4 5
2 1 10
3 1 3
4 2 6
1 4 7
2 3 3
输出 
1 3
1 2 3 
3 3
6 4 5 
1 5
4 2 1 6 3 
1 4
1 4 3 2 
3 3
2 3 1

解题思路：

学过Kruskal算法的应该很快能想到这个题目的思路，Kruskal算法的思想就是将所有边按照从小到大排序从而构造最小生成树，这里用到了类似的思想，这里可以将所有边按照从大到小排序，当枚举到某一条边时，这条边连接的俩个端点a,b，如果a,b之前已经连通，那么这里再加上这条边就会形成环，并且当前这条边是这个环中权重最小的，为什么当前这条边是权重最小的呢，因为我们是从大到小枚举边的呀，所以当前这条边的权重肯定是最小的，如果a,b之前不是连通的，我们将a,b所在连通块进行合并，合并过程可以使用并查集进行维护，到这里我们就找到了一个环中的最小权重边，那么我们再dfs找环即可。

时间复杂度：O(n+mlog(m))，n表示点数，m表示边数。

空间复杂度：O(n+m)，n表示点数，m表示边数。

cpp代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;
typedef long long LL;const int N=2e5+10;int T,n,m;
struct Edges{int a,b,c;
}edges[N];
vector<int>g[N];
int p[N],ans[N],tot;
bool vis[N];
int st,ed,w;int find(int x)
{if(p[x]!=x)p[x]=find(p[x]);return p[x];
}bool dfs(int u,int fa)
{if(u==ed){cout<<w<<' '<<tot<<'\n';for(int i=1;i<=tot;i++)cout<<ans[i]<<' ';cout<<'\n';return true;}for(auto& j:g[u]){if(j==fa || vis[j])continue;vis[j]=true;ans[++tot]=j;if(dfs(j,u))return true;tot--;}return false;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)g[i].clear();  //多测，用于建立邻接表的vector也要记得清空for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;g[a].push_back(b);g[b].push_back(a);edges[i]={a,b,c};}sort(edges+1,edges+1+m,[&](Edges A,Edges B){  //按边权从大到小排序return A.c>B.c;});w=1e9;for(int i=1;i<=n;i++)p[i]=i;  //初始化并查集for(int i=1;i<=m;i++)  //从大到小枚举所有边，找到某个环中的最小权重边{int a=edges[i].a,b=edges[i].b,c=edges[i].c;int pa=find(a),pb=find(b);if(pa!=pb){p[pb]=pa;}else {st=a,ed=b,w=c;}}//dfs找环for(int i=1;i<=n;i++)vis[i]=false;tot=0;ans[++tot]=st,vis[st]=true;dfs(st,ed);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;while(T--){solve();}return 0;
}

这篇关于Codeforces Round 923 (Div. 3) F. Microcycle【Kruskal算法思想+并查集+dfs找环】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---