并查集練兵場 - acm1314－IT工程師數位筆記本

文章出處

并查集：

N 個不同的元素分布在若干個互不相交集合
中，需要進行以下3個操作：
 1. 合并兩個集合
 2. 查詢一個元素在哪個集合
 3. 查詢兩個元素是否屬于同一集合

一般用下面兩個模板：

int get_par(int a)
{
    if(par[a]!=a) par[a] = get_par(par[a]);
    return par[a];
} 
/* 也可以表示成這種形式，兩種形式與數組的初始化有關。 
int get_par(int a)
{
    if(par[a]==-1) return a;
    return par[a] = get_par(par[a]);
}
*/
int query(int a, int b)
{
    return get_par(a)==get_par(b);
}

void merge(int a, int b)
{
    par[get_par(a)]=get_par(b);
}

《1》簡單模板題。

http://poj.org/problem?id=1611

#include<iostream>
using namespace std;

const int MAXN = 30000;
int n, m, k;
int parent[MAXN+10];
int total[MAXN+10];

int GetParent(int a)
{
    if(parent[a]!=a)
    parent[a]=GetParent(parent[a]);
    return parent[a];
} 

void Merge(int a, int b)
{
    int p1 = GetParent(a);
    int p2 = GetParent(b);
    if(p1==p2)
    return;
    total[p1]+=total[p2];
    parent[p2] = p1;
}

int main()
{
    while(true)
    {
        scanf("%d%d", &n, &m);
        if(n==0&&m==0) break;
        for(int i=0; i<n; i++)
        parent[i] = i, total[i]=1;
        for(int i=0; i<m; ++i)
        {
            int h,s;
            scanf("%d", &k);
            scanf("%d", &h);
            for(int j=1; j<k; j++)
            {
                scanf("%d", &s);
                Merge(h, s);
            }
        }
            printf("%d\n", total[GetParent(0)]);
    }
        return 0;
}

View Code

《2》再來道裸題。

http://poj.org/problem?id=2524

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 50000 + 10;
int Fa[MAXN];

int find(int x)
{
    if(Fa[x]==-1) return x;
    return Fa[x]=find(Fa[x]);
}

void Merge(int u, int v)
{
    int t1 = find(u);
    int t2 = find(v);
    if(t1!=t2) Fa[t1] = t2;
}

int main()
{
    //freopen( "in.txt", "r", stdin );
    //freopen( "out.txt", "w", stdout );
    int n, m, u, v;
    int kase = 0;
    while(scanf("%d%d", &n, &m)==2)
    {
        if(n==0&&m==0) break;
        kase++;
        memset(Fa, -1, sizeof(Fa));
        while(m--)
        {
            scanf("%d%d", &u, &v);
            Merge(u, v);
        }
        int ans = 0;
        for(int i=1; i<=n; i++)
        if(Fa[i]==-1) ans++;
        
        printf("Case %d: %d\n", kase, ans);
    }
    return 0;
}

View Code

《3》這個題對小恪來說有點難，但是收獲不小哦！

http://poj.org/problem?id=1988

這道題很容易想到暴力的方法，很不幸的是一定會超時。嘿嘿！

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 30000+10;
int parent[MAXN];
int sum[MAXN]; //表示磚塊 i 所在堆的磚塊總數。
int under[MAXN];//under[i]表示磚塊 i 下面有多少磚塊。

int GetParent(int a)
{
    if(parent[a]==a) return a;
    int t=GetParent(parent[a]);
    under[a]+=under[parent[a]];
    parent[a] = t;
    return parent[a];
} 

//把 b 所在的堆，疊放到 a 所在的堆。 
void Merge(int a, int b)
{
    int n;
    int pa = GetParent(a);
    int pb = GetParent(b);
    if(pa==pb) return;
    parent[pb] = pa;
    under[pb] = sum[pa];//under[pb]在賦值前一定是 0 ，
    //因為parent[pb] = pb, pb一定是最底下的。 
    sum[pa]+=sum[pb];
}

int main()
{
    int p;
    for(int i=0; i<MAXN; i++)
    {
        sum[i] = 1;
        under[i] = 0;
        parent[i] = i;
    }
    scanf("%d", &p);
    for(int i=0; i<p; i++)
    {
        char s[20]; int a, b;
        scanf("%s", s);
        if(s[0] == 'M')
        {
            scanf("%d%d", &a, &b);
            Merge(b, a);
        }
        else
        {
            scanf("%d", &a);
            GetParent(a);
            printf("%d\n", under[a]);
        }
    }
    return 0;
}

View Code

《4》這個題可以用純粹的并查集解，但是如何判定合并條件有點虐心！

http://acm.hdu.edu.cn/showproblem.php?pid=1198

#include<cstdio>
const int MAXN = 100 + 10;
char map[MAXN][MAXN];
int Fa[MAXN*MAXN];

int find(int x)
{
    if(Fa[x]==-1) return x;
    return Fa[x] = find(Fa[x]);
}

void Merge(int a, int b)
{
    int t1 = find(a);
    int t2 = find(b);
    if(t1!=t2) Fa[t1] = t2;
}

int main()
{
    int m, n;
    while(scanf("%d%d", &m, &n))
    {
        if(m<0||n<0) break;
        for(int i=0; i<m; i++)
        scanf("%s", &map[i]);
        for(int i=0; i<m*n; i++)
        Fa[i]= - 1;
        for(int i=0; i<m; i++)
        for(int j = 0; j<n; j++)
        {
            //判定條件有點虐心！   開口向： 上 下  左  右。 
            if(i>0&&(map[i][j]=='A'||map[i][j]=='B'||map[i][j]=='E'||map[i][j]=='G'||map[i][j]=='H'||map[i][j]=='J'||map[i][j]=='K'))
            if(map[i-1][j]=='C'||map[i-1][j]=='D'||map[i-1][j]=='E'||map[i-1][j]=='H'||map[i-1][j]=='I'||map[i-1][j]=='J'||map[i-1][j]=='K')
            Merge(i*n+j, (i-1)*n+j);
            if(j>0&&(map[i][j]=='A'||map[i][j]=='C'||map[i][j]=='F'||map[i][j]=='G'||map[i][j]=='H'||map[i][j]=='I'||map[i][j]=='K'))
            if(map[i][j-1]=='B'||map[i][j-1]=='D'||map[i][j-1]=='F'||map[i][j-1]=='G'||map[i][j-1]=='I'||map[i][j-1]=='J'||map[i][j-1]=='K')
            Merge(i*n+j,i*n+j-1);
        }
        int res = 0;
        for(int i=0; i<m*n; i++)
        if(Fa[i]==-1) res++;
        printf("%d\n", res);
    }
    return 0;
}

View Code

《5》赤裸裸的模板題

http://acm.hdu.edu.cn/showproblem.php?pid=1232

#include<cstdio>
const int MAXN = 1000 + 10;
int Fa[MAXN];

int find(int x)
{
    if(Fa[x]==-1) return x;
    return Fa[x] = find(Fa[x]);
}

void Merge(int a, int b)
{
    int t1 = find(a);
    int t2 = find(b);
    if(t1!=t2) Fa[t1] = t2;
}

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m)!=EOF, n)
    {
        for(int i=1; i<=n; i++)
        Fa[i] = -1;
        int a, b;
        while(m--)
        {
            scanf("%d%d", &a, &b);
            Merge(a, b);
        }
        int res = 0;
        for(int i=1; i<=n; i++)
        if(Fa[i]==-1) res++;
        printf("%d\n", res-1);
    }
    return 0;
}

View Code

《6》來道難的吧（歐拉回路+字典樹+并查集）

http://poj.org/problem?id=2513

此題好坑！本想巧妙地繞過字典序，然而題目中并未告訴你一共有那幾種顏色（感覺這一點好賤！），結果此題機智的卡死了我這等弱渣，弱渣是何等的悲哀啊！先貼一下我的wong代碼（適合各種顏色首字母都不同的情況，此題數據中應有首字母相同的情況）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

const int maxn = 1000 + 5;

int pa[256];
int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; } 

int used[256], deg[256]; // 是否出現過；度數

int main()
{
    int flag = 0;
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    char s1[105], s2[105];
    memset(used, 0, sizeof(used));
    memset(deg, 0, sizeof(deg));
    for(int ch = 'a'; ch <= 'z'; ch++) pa[ch] = ch; // 初始化并查集

    int cc = 26; // 連通塊個數

    while(scanf("%s%s", s1, s2)!=EOF)
    {
        flag = 1;
        char c1 = s1[0], c2 = s2[0];
        deg[c1]++;
          deg[c2]--;
          used[c1] = used[c2] = 1;
          int s1 = findset(c1), s2 = findset(c2);
          if(s1 != s2) { pa[s1] = s2; cc--; }
    }
    vector<int> d;
    for(int ch = 'a'; ch <= 'z'; ch++) {
      if(!used[ch]) cc--; //沒出現過的字母 
      else if(deg[ch] != 0) d.push_back(deg[ch]);
    }
    bool ok = false;
    if(cc == 1 && (d.empty() || (d.size() == 2 && (d[0] == 1 || d[0] == -1)))) ok = true;
    if(ok&&flag) printf("Possible\n");
    else printf("Impossible\n");
    return 0;
  }

View Code

下面是一巨巨的AC代碼：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=500010;
int F[MAXN];
const int MAX=26;
int degree[MAXN];//度數
int color;//顏色編號，從0開始，最后就是顏色總數
int find(int x)
{
    if(F[x]==-1)return x;
    return F[x]=find(F[x]);
}
void bing(int a,int b)
{
    int t1=find(a);
    int t2=find(b);
    if(t1!=t2) F[t1]=t2;
}
typedef struct Trie_Node
{
    bool isWord;
    struct Trie_Node *next[MAX];
    int id;
}Trie;
int insert(Trie *root,char *word)//返回顏色編號
{
    Trie *p=root;
    int i=0;
    while(word[i]!='\0')
    {
        if(p->next[word[i]-'a']==NULL)
        {
            Trie *temp=new Trie;
            temp->isWord=false;
            for(int j=0;j<MAX;j++)
              temp->next[j]=NULL;
            temp->isWord=false;
            temp->id=0;
            p->next[word[i]-'a']=temp;
        }
        p=p->next[word[i]-'a'];
        i++;
    }
    if(p->isWord)
    {
        return p->id;
    }
    else
    {
        p->isWord=true;
        p->id=color++;
        return p->id;
    }
}
void del(Trie *root)
{
    for(int i=0;i<MAX;i++)
    {
        if(root->next[i]!=NULL)
         del(root->next[i]);

    }
    free(root);
}
int main()
{
   // freopen("in.txt","r",stdin);
   // freopen("out.txt","w",stdout);
    char str1[20],str2[20];
    Trie *root=new Trie;
    for(int i=0;i<MAX;i++)
      root->next[i]=NULL;
    root->isWord=false;
    root->id=0;
    color=0;
    memset(F,-1,sizeof(F));
    memset(degree,0,sizeof(degree));
    while(scanf("%s%s",&str1,&str2)!=EOF)
    {
        int t1=insert(root,str1);
        int t2=insert(root,str2);
     //   printf("%d %d\n",t1,t2);
        degree[t1]++;
        degree[t2]++;
        bing(t1,t2);

    }
//***********************************************
//這個是根據F數組等于-1來找根結點
    int cnt1=0,cnt2=0;
    for(int i=0;i<color;i++)
    {
        if(F[i]==-1)cnt1++;
        if(degree[i]%2==1)cnt2++;
        if(cnt1>1)break;
        if(cnt2>2)break;
    }
    //數據比較坑人，存在0根木棒的情況，此時cnt1==0
    if((cnt1==0||cnt1==1)&&(cnt2==0||cnt2==2))
      printf("Possible\n");
    else printf("Impossible\n");
    //del(root);//單組輸入可以不釋放空間，可以節省時間
    return 0;

/*
    //********************************
    //這種是找尋根結點，多個根節點來判斷是不是連通
    bool flag=true;
    int tt1=find(0);
    int cnt=0;//統計度數為奇數的結點個數
    for(int i=0;i<color;i++)
    {
        if(find(i)!=tt1)flag=false;//不連通也不是歐拉回路
        if(!flag)break;
        if(degree[i]%2==1) cnt++;
        if(cnt>2) flag=false;//度數為奇的結點個數>2，肯定不是歐拉回路了
    }
    if(cnt==1)flag=false;
    if(flag) printf("Possible\n");
    else printf("Impossible\n");
    del(root);//單組輸入可以不釋放空間，可以節省時間
    return 0;
    //******************************************
    */
}

View Code

我還是 too yang！草灘小恪仍需惡補！！！

《7》用并查集判斷種類

http://poj.org/problem?id=1703

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;

const int MAXN=100010;
int Fa[MAXN];
int val[MAXN];
int find(int x)
{
    if(Fa[x]==-1)return x;
    int tmp=find(Fa[x]);
    val[x]=(val[x]+val[Fa[x]])%2;
    return Fa[x]=tmp;
}
void Merge(int x,int y)
{
    int t1=find(x);
    int t2=find(y);
    if(t1!=t2)
    {
        Fa[t1]=t2;
        val[t1]=(val[y]-val[x]+1)%2;
    }
}
int main()
{
    int T;
    char str[10];
    int u,v;
    int n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(Fa,-1,sizeof(Fa));
        memset(val,0,sizeof(val));
        while(m--)
        {
            scanf("%s%d%d",&str,&u,&v);
            if(str[0]=='A')
            {
                if(find(u)!=find(v))
                {//題目說兩個集團至少有一個人，所以N==2的時候單獨考慮，但是不考慮這個也可以AC，估計沒有這樣的數據
                    if(n==2)printf("In different ganges.\n");
                    else printf("Not sure yet.\n");
                }
                else
                {
                    if(val[u]!=val[v])printf("In different gangs.\n");
                    else printf("In the same gang.\n");
                }
            }
            else
            {
                Merge(u,v);
            }
        }
    }
    return 0;
}