自动搬运

查看原文

来自洛谷，原作者为

	Nightsky_Stars .

搬运于2025-08-24 22:50:33，当前版本为作者最后更新于2024-02-01 10:36:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给一个 $n$ 个点 $m$ 条边的无向图，按照输入顺序，第 $i$ 条边的权值 $2^i$，找出一个长度 $s \ge 3$ 的简单环，使权值最小，并按升序输出构成这个简单环的边的的编号。若无解则输出 $-1$。

思路

考虑贪心，从小到大枚举每条边的边权。

由于 $\sum_{i=1}^n2^i \le 2^{n+1}$，所以贪心成立。

使用 Kruskal 算法，一边输入一遍处理，用并查集维护，若并查集查到属于同一联通块时，就说明出现了环，此时用 dfs 找到这个环输出。

CODE:

#include<bits/stdc++.h>
using namespace std;
int m,n,T,fa[2500010];
struct edge{
	int u,v;
}g[100010];
vector<int> s;
vector<edge> e[100010];
inline int find(int x){//并查集
	if(x!=fa[x]){
		fa[x]=find(fa[x]);
	}
	return fa[x];
}
inline void join(int x,int y){
	int fx=fa[x],fy=fa[y];
	if(fx!=fy) fa[fx]=fy;
	else return ;
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(){//升序输出
	sort(s.begin(),s.end());
	for(int i=0;i<s.size();i++){
		cout<<s[i]<<" ";
	}
	cout<<"\n";
	return ;
}
inline void init(){
	s.clear();
	for(int i=1;i<=m;i++){
        g[i].u=g[i].v=0;
    }
	for(int i=1;i<=n;i++){
		fa[i]=i;
		e[i].clear();
	}
}
inline bool dfs(int x,int now,int f){//dfs求环
	if(now==x) return 1;
	for(auto to:e[now]){// 遍历 now 的所有边
		if(to.u==f) continue;
		s.push_back(to.v);
		if(dfs(x,to.u,now)) return 1;
		s.pop_back();
	}
	return 0;
}
inline void kruskal(){
	for(int i=1;i<=m;i++){
		if(find(g[i].u)==find(g[i].v)){//如果查询并查集在同一联通块内
			if(dfs(g[i].v,g[i].u,g[i].u)){
				s.push_back(i);
				write();
				break;
			}
			continue;
		}
		e[g[i].u].push_back((edge){g[i].v,i});
		e[g[i].v].push_back((edge){g[i].u,i});
		join(find(g[i].u),find(g[i].v));//合并
		if(i==m) cout<<"-1\n";
	}
}
int main(){
	T=read();
	while(T--){
		n=read();
		m=read();
		init();//多组测试数据，记得清空
		for(int i=1;i<=m;i++){
			g[i].u=read();
			g[i].v=read();
		}
		kruskal();
	}
	return 0;
}