非递归并查集——zoj4109

卡常卡的我难受

非递归并查集好像写起来常数小一点

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=;

    for(int i=;i<=n;i++)G[i].clear(),F[i]=i,vis[i]=;

    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=;i<=m;i++){

            int u,v;

            scanf("%d%d",&u,&v);

            addedge(u,v);addedge(v,u);

            Union(u,v);

        }

        for(int i=;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]=;

            ans[++tt]=cur;

            for(int i=;i<G[cur].size();i++){

                int v=G[cur][i];

                if(vis[v])continue;

                pq.push(v);

            }

        }

        for(int i=;i<tt;i++)cout<<ans[i]<<" ";

        cout<<ans[tt]<<endl;

    }

}