poj 2524 Ubiquitous Religions(并查集)

Memory: 4664K

Time: 532MS

解题思路

题意：

    问一个大学里学生的宗教，通过问一个学生可以知道另一个学生是不是跟他信仰同样的宗教。问学校里最多可能有多少个宗教。

也就是给定一个图的点数和相应的边，问有多少个连通分量。

 

思路：

   使用并查集，输入时使每个节点的根节点都指向自己，枚举每条边，把根节点不相同的合并。完后列举每个节点，把每个节点的根节点放在数组arr里，arr用qsort排序，数出有多少个不相同的根节点，就是结果。本来合并的时候没有用到rank，700多MS，用之后减少到500多。所以并查集里面那些优化都一定要用啊。

源程序

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define N 50010
#define M N*10

typedef struct
{
    int x, y;
}node;
node nodes[M];
int arr[N], parent[N], rank[N];

int find(int x)
{
    int y, z;
    
    y = x;
    while(parent[y] != y)
        y = parent[y];
    while(x!=y)
    {
        z = parent[x];
        parent[x] = y;
        x = z;
    }
    return y;
}

void _union(int x, int y)
{
    if(rank[x] > rank[y])
        parent[y] = x;
    else {
        if(rank[x] == rank[y])
            rank[y]++;
        parent[x] = y;
    }
}

int cmp(const void *p, const void *q)
{
    return *(int *)p > *(int *)q ? -1 : 1;
}

int main()
{
    int i, j;
    int n, m, c, count, k=0, a, b;
    freopen("in.txt", "r", stdin);
    while(scanf("%d%d", &n, &m) && n && m)
    {
        memset(nodes, 0, sizeof(nodes));
        memset(parent, 0, sizeof(parent));
        memset(arr, 0, sizeof(arr));
        memset(rank, 0, sizeof(rank));
        for(i=0; i<m; i++)
        {
            scanf("%d%d", &nodes[i].x, &nodes[i].y);
            parent[nodes[i].x] = nodes[i].x;
            parent[nodes[i].y] = nodes[i].y;
        }
        for(i=0; i<m; i++)
        {
            a = find(nodes[i].x);
            b = find(nodes[i].y);
            if(a != b)
                _union(a, b);
        }

        for(i=0; i<n; i++)
        {
            arr[i] = find(i+1);
            if(!arr[i])
                arr[i] = i+1;
        }
        qsort(arr, n, sizeof(arr[0]), cmp);
        count = 1;
        c = arr[0];
        for(i=1; i<n; i++)
        {
            if(arr[i] != c)
            {
                count++;
                c = arr[i];
            }
        }
        k++;
        printf("Case %d: %d\n", k, count);
        
    }
    getch();
    return 0;
}