1 条题解
-
0
#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
- 上传者