卡常卡的我难受
非递归并查集好像写起来常数小一点
int F[maxn]; int Find(int x){ int r = x; while (F[r] != r)r = F[r]; int i = x,j; while (F[i] != r){ j = F[i]; F[i] = r; i = j; } return r; } void Union(int u,int v){ int f1=Find(u),f2=Find(v); if(f1!=f2){ if(f1>f2)swap(f1,f2); F[f2]=f1; } }下面是完整代码
#include<bits/stdc++.h> using namespace std; #define maxn 1000005 vector<int> G[maxn]; int n,m; int F[maxn]; int Find(int x){ int r = x; while (F[r] != r)r = F[r]; int i = x,j; while (F[i] != r){ j = F[i]; F[i] = r; i = j; } return r; } void Union(int u,int v){ int f1=Find(u),f2=Find(v); if(f1!=f2){ if(f1>f2)swap(f1,f2); F[f2]=f1; } } int vis[maxn],ans[maxn],tt; priority_queue<int,vector<int>, greater<int> >pq; void init(){ tt=0; for(int i=0;i<=n;i++)G[i].clear(),F[i]=i,vis[i]=0; while(pq.size())pq.pop(); } void addedge(int u,int v){G[u].push_back(v);} int main(){ int t; cin>>t;while(t--){ scanf("%d%d",&n,&m); init(); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v);addedge(v,u); Union(u,v); } for(int i=1;i<=n;i++) if(Find(i)==i)pq.push(i); cout<<pq.size()<<endl; while(!pq.empty()){ int cur=pq.top();pq.pop(); if(vis[cur])continue; vis[cur]=1; ans[++tt]=cur; for(int i=0;i<G[cur].size();i++){ int v=G[cur][i]; if(vis[v])continue; pq.push(v); } } for(int i=1;i<tt;i++)cout<<ans[i]<<" "; cout<<ans[tt]<<endl; } } View Code
转载于:https://www.cnblogs.com/zsben991126/p/10782884.html
相关资源：各显卡算力对照表！