並查集總結

並查集總結

並查集

並查集：感覺就是一種高效的集合處理辦法。

一.並查集實現：

按秩合並優化：

以HDU 1325 為例

#include
#include
#include
using namespace std;

const int N=1000;
int vis[N];
int uset[N],rank[N];

void make_set(int size)
{
    for(int i=0;irank[y])                   //秩小的，加在秩大的樹上
        uset[y]=x;
    else
    {
        uset[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}






int main()
{
    int u,v;
    int cas=0;
    while(scanf("%d%d",&u,&v))
    {
        int maxx=0;

        int ok=1;
        if(u<0&&v<0)
            break;
        if(u==v&&v==0)
        {
            printf("Case %d is a tree.\n",++cas);
            continue;
        }
        make_set(N);
        memset(vis,0,sizeof(vis));
        union_set(u,v);
        if(u==v)
            ok=0;
        vis[v]=1;
        while(scanf("%d%d",&u,&v),u||v)
        {
            if(v==u)
                ok=0;
            if(vis[v])
                ok=0;
            vis[v]=1;
            union_set(u,v);
            if(max(u,v)>maxx)
                maxx=max(u,v);
        }
        int cnt=0;
        for(int i=1;i<=maxx;i++)
            if(uset[i]==i)
                cnt++;
        if(cnt>1) ok=0;
        if(ok)
            printf("Case %d is a tree.\n",++cas);
        else
            printf("Case %d is not a tree.\n",++cas);




    }            
    return 0;

}

以HDU 1856 為例

#include
#include
#include
#include
using namespace std;


const int N=100010;
int uset[N];

void make_set(int n)
{
    for(int i=0;iint find(int x) {      /非遞歸版    int p = x, t;    while (uset[p] >= 0) p = uset[p];    while (x != p) {        t = uset[x];        uset[x] = p;        x = t;    }    return x;}*/

 void union_set(int x,int y)
{
    if((x=find_set(x))==(y=find_set(y)))
        return;
    
    if(uset[x]




二：並查集的應用