P9666题解

Nightsky_Stars · 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;
}