poj1611 并查集基础 0ms

方法一： 16ms

#include<cstdio>
#define maxn 30000
using namespace std;
int tree[maxn+5];//并查集的树
int sum[maxn+5];//嫌疑人数
void init(int n) //并查集的初始化
{
    for(int i = 0; i<n; ++i)
    {
        tree[i] = i;
        sum[i] = 1;
    }
}
int find(int x)//查找
{
    return tree[x]==x?x:tree[x] = find(tree[x]);//路径压缩
}
void merge(int a,int b)
{
    int x,y;
    x = find(a);
    y = find(b);
    if(x!=y)
    {
        tree[x] = y;
        sum[y] += sum[x];
    }
}
int main()
{
    int n,m,k,x,y;
    int p1,p2;
    while(scanf("%d%d",&n,&m),n)
    {
        init(n);
        while(m--)
        {
            scanf("%d%d",&k,&p1);
            for(int i = 1; i<k; ++i)
            {
                scanf("%d",&p2);
                merge(p1,p2);
            }
        }
        k = find(0);
        printf("%d\n",sum[k]);
    }
    return 0;
}

方法2： 0ms`

#include<cstdio>
#define maxn 30000
using namespace std;
int tree[maxn+5];//并查集的树
int sum[maxn+5];//嫌疑人数
void init(int n)  //并查集的初始化
{
    for(int i = 0; i<n; ++i)
    {
        tree[i] = i;
        sum[i] = 1;
    }
}
int find(int x)//查找
{
    return tree[x]==x?x:tree[x] = find(tree[x]);//路径压缩
}
int main()
{
    int n,m,k,x,y;
    int p1,p2;
    while(scanf("%d%d",&n,&m),n)
    {
        init(n);
        while(m--)
        {
            scanf("%d%d",&k,&p1);
            for(int i = 1; i<k; ++i)
            {
                scanf("%d",&p2);
                x = find(p1);
                y = find(p2);
                if(x!=y)
                {
                    tree[x] = y;
                    sum[y] += sum[x];
                }
            }
        }
        k = find(0);
        printf("%d\n",sum[k]);
    }
    return 0;
}

为什么方法一样但时间有微小差异，两代码唯一不同的是merge函数，0ms并未将merge写在函数外。
这样省去了每次调用函数的时间，可以大致算出每次调用要0.8微秒（16ms/30000)
因此在考虑大数据量时，想加快运行时间，可以考虑将函数写在主函数里，
但不推荐这样，因为会丧失程序的可读性