1 条题解

  • 0
    @ 2024-6-14 16:26:21
    #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;
    }
    
    • 1

    信息

    ID
    822
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者