数据结构

并查集

　　并查集一般用于对动态连通性的判断，主要应用于判断两个元素是否在同一个集合，两个点是否连通，变量名等同性以及间接好友的判断。同时并查集经常作为其他模板的一部分实现某些功能。
　　并查集常用于的题型为判断某两个元素是否属于同一个集合，判断图是否连通或是否有环，或配合其他算法如最小生成树Kruskal，与DP共同使用等。

• 并查集模板

    int fa[N];
    void init(int n) {  // 不要忘记哦！！！
        for (int i = 0; i <= n; i++)
            fa[i] = i;
        }
    }
    void unin(int u, int v) {
        int fau = find(u);
        int fav = find(v);
        if (fau == fav) return;
        fa[fav] = fau;
    }
    int find(int u) {
        if (fa[u] != u) {
            fa[u] = find(fa[u]);
        }
        return fa[u];
    }
  

• 更短一些的并查集模板

    int fa[N];
  
    void init(int n) {
        for (int i = 0; i <= n; fa[i] = i++);
    }
  
    void unin(int u, int v) {
        fa[find(v)] = find(u);
    }
  
    int find(int u) {
        return fa[u] == u ? fa[u] : fa[u] = find(fa[u]);
    }
  

例题

• poj 1611 The Suspects
  　　有很多组学生，在同一个组的学生经常会接触，也会有新的同学的加入。但是SARS是很容易传染的，只要在改组有一位同学感染SARS，那么该组的所有同学都被认为得了SARS。现在的任务是计算出有多少位学生感染SARS了。假定编号为0的同学是得了SARS的。
  　　采用num[]存储该集合中元素个数，并在集合合并时更新num[]即可。然后找出0所在的集合的根节点x，因此，num[x]就是answer了。

代码如下：

#include <iostream>

using namespace std;

int n, m, k, t, f, p[30001], rank[30001], a, b;

int find(int x) {
    if (x == p[x]) return x;
    else return p[x] = find(p[x]);
}

void un(int x, int y) {
    a = find(x);
    b = find(y);
    if (a == b)
        return;
    if (rank[a] > rank[b])
        p[b] = a;
    else {
        p[a] = b;
        if (rank[a] == rank[b])
            rank[b]++;
    }
}

int main() {
    int i, sum;
    while (cin >> m >> n && (m || n)) {
        for (i = 0; i < m; i++) {
            p[i] = i;
            rank[i] = 0;
        }
        for (i = 0; i < n; i++) {
            cin >> k;
            if (k >= 1)
                cin >> f;
            for (int j = 1; j < k; j++) {
                cin >> t;
                un(f, t);
            }
        }
        sum = 1;
        for (i = 1; i < m; i++) {
            if (find(i) == find(0))
                sum++;
        }
        cout << sum << endl;
    }
    return 0;
}

• poj 1182 食物链(并查集经典题目)
  　　题目告诉有3种动物，互相吃与被吃，现在告诉你m句话，其中有真有假，叫你判断假的个数(如果前面没有与当前话冲突的，即认为其为真话)
  　　 带权并查集和普通并查集最大的区别在于带权并查集合并的是可以推算关系的点的集合（可以通过集合中的一个已知值推算这个集合中其他元素的值）。而一般并查集合并的意图在于这个元素属于这个集合。带权并查集相当于把“属于”的定义拓展了一下，拓展为有关系的集合。
  　　本题用rank[x]记录x与x的最远的祖先的关系。 这里定义rank[x]=0表示x与x的祖先是同类。rank[x]==1表示x吃x的祖先。rank[x]==2表示x的祖先吃x；这样定义后就与题目中输入数据的D联系起来，(D-1)就可以表示x与y的关系。这样就可以用向量的形式去推关系的公式了。我们用f(x,father[x])表示rank[x]的值；
  
  代码如下:

#include<stdio.h>  

int fa[50005]={0};  
int rank[50005]={0};  
int n;  

void initial()  
{  
    for(int i=1;i<=n;i++)  
    {  
        fa[i]=i; rank[i]=0;  
    }  
}  

int getfather(int x)  
{  
    if(x==fa[x])  return x;  
    int oldfa = fa[x];  
    fa[x]=getfather(fa[x]);  
    rank[x]=(rank[x]+rank[oldfa])%3;  //用向量的形式很快就可以看出来  
    return fa[x];  
}  

void unionset(int r,int x,int y)  
{  
    int fx,fy;  
    fx=getfather(x); fy=getfather(y);  
    if(fx==fy) return;  
    fa[fx]=fy;  
    rank[fx]=(rank[y]+r-rank[x]+3)%3;   // 这里同样可以用向量来推公式。另外需要注意的是，这里只更新了fx的rank值，而fx的儿子的rank值都没有更新会不会有问题。其实不碍事，由于我们每次输入一组数据我们都对x和y进行了getfather的操作（x>n || y>n ……)的除外。在执行getfather的操作时，在回溯的过程中就会把fx的儿子的rank值都更新了。  
    return ;  
}  

int istrue(int d,int x,int y)  
{  
    int fx,fy,r;  
    if(x>n || y>n || ((x==y)&&(d==2)) )  
        return 0;  
    fx=getfather(x); fy=getfather(y);  
    if(fx!=fy)  return 1;  
    else  
    {  
        if(rank[x]==((d-1)+rank[y])%3) return 1;  // 这个公式可以用向量来推：如果（ f(x,y) + f(y,father[y]））% 3 == f(x,father[x]) 则是正确的，否则是错的。这个形式可以用向量来表示，就是判断这个向量加法对不对   x--->y + y---> fx(fy) 是否等于  x--->fx(fy)  
        else  return 0;  
    }  
}  

int main()  
{  
    int k,i,x,y,d; int ans=0;  
    scanf("%d%d",&n,&k);  
    initial();  
    for(i=1;i<=k;i++)  
    {  
        scanf("%d%d%d",&d,&x,&y);  
        if( !istrue(d,x,y) )  
            ans++;  
        else  
            unionset(d-1,x,y);  
    }  
    printf("%d\n",ans);  
    return 0;  
}