并查集

poj 1611 : the suspects
题意：
一个学校爆发了sars，这个学校有很多个group，每个人可以参加多个group，如果一个group中有一个人是患者，那么这个group中其他人全部认定为患者。现在已知0为患者，输入多个group的成员，判断一共有多少个患者。
思路：
并查集，每输入一个group，就将这个group的其他成员与第一个成员合并。最后查询所有成员的根与0的根相同的个数。
代码：

#include <stdio.h>
#include <string.h>
int par[30005];
int inp[30005];
int rank[30005];
int find(int x)
{
    //printf("eeeeeeeee\n");
    if (par[x] == x)
        return x;
    else
        return find(par[x]);
}
int unit(int x,int y)
{
        if (rank[x] < rank[y])
        {
            par[x] = y;
        }
        else
        {
            par[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
}
int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m) != EOF)
    {
        if (m == n && n == 0) break;
        memset(par,0,sizeof(par));
        memset(rank,0,sizeof(rank));
        for (int i = 0;i < n;i++)
            par[i] = i;
        for (int i = 1;i <= m;i++)
        {
            int k;
            int minn = 500000;
            scanf("%d",&k);
            memset(inp,0,sizeof(inp));
            for (int j = 1;j <= k;j++)
                scanf("%d",&inp[j]);
            for (int j = 2;j <= k;j++)
            {
                unit(find(inp[1]),find(inp[j]));
            }
        }
        int res = 0;
        int root0 = find(0);
        for (int i = 0;i < n;i++)
            if (find(i) == root0) res++;
        printf("%d\n",res);
        //for (int i = 0;i < n;i++)
          //  printf("%d ",par[i]);
    }
    return 0;
}

poj 2524 : Ubiquitous Religions
题意：
一个学校有n个学生，现在你知道某某两个学生所信仰的宗教是相同的，问这个学校的学生所信仰的宗教最多有多少个。
思路：
并查集裸题，把每两个学生直接合并，最后计数有多少个不同的根。
代码：

#include <stdio.h>
#include <string.h>
int rank[50005];
int par[50005];
int res[50005];
int find(int x)
{
    if (par[x] == x)
        return x;
    else
        return find(par[x]);
}
void unit(int x,int y)
{
    if (rank[x] < rank[y])
    {
        par[x] = y;
    }
    else
    {
        par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}
int main()
{
    int n,m;
    int ca = 1;
    while (scanf("%d%d",&n,&m) != EOF && n && m)
    {
        memset(rank,0,sizeof(rank));
        memset(par,0,sizeof(par));
        memset(res,0,sizeof(res));
        for (int i = 1;i <= n;i++)
            par[i] = i;
        for (int i = 1;i <= m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if (find(x) == x && find(y) == y)
            {
                par[y] = x;
            }
            else
            {
                int rootx = find(x);
                int rooty = find(y);
                unit(rootx,rooty);
            }
        }
        for (int i = 1;i <= n;i++)
        {
            res[find(i)]++;
        }
        int s = 0;
        for (int i = 1;i <= n;i++)
        {
            if (res[i])
                s++;
        }
        printf("Case %d: %d\n",ca++,s);
    }
    return 0;
}

hdu 1272
思路：
被这题卡了半天，妈的智障。
首先，还是没有仔细审题的问题，这题抽象出来就是判断一个图是否为无环的只有一个连通分量的图。直接用并查集做就好了。谨记审题仔细。
代码：

#include <stdio.h>
#include <string.h>
int par[200005];
int ran[200005];
bool v[100005];
void init(void)
{
    for (int i = 0;i < 200005;i++)
        par[i] = i;
}
int fin(int x)
{
    if (x == par[x])
        return x;
    else
        return par[x] = fin(par[x]);
}
bool unit(int x,int y)
{
    x = fin(x);
    y = fin(y);
    if (x == y) return 0;
    if (ran[x] < ran[y])
    {
        par[x] = y;
    }
    else
    {
        par[y] = x;
        if (ran[x] == ran[y]) ran[x]++;
    }
    return 1;
}
int main()
{
   while (1)
   {
       memset(par,0,sizeof(par));
       memset(ran,0,sizeof(ran));
        memset(v,0,sizeof(v));
       bool f = 0,fa = 0;
       int ma = 0;
       init();
       int a,b;
       while (scanf("%d%d",&a,&b) == 2)
       {
           if (a == -1 && b == -1)
           {
               f = 1;
               break;
           }
            if (a * b == 0) break;
            v[a] = 1;v[b] = 1;
            if (b > ma) ma = b;
            if (a > ma) ma = a;
           if (!unit(a,b))
           {
               fa = 1;
           }
       }
       if (f) break;
       if (fa)
       {
           printf("No\n");
       }
       else
       {
           int rt = fin(ma);
           bool ff = 0;
           for (int i = 1;i <= ma;i++)
            if (v[i] && fin(i) != rt) ff = 1;
            if (ff) printf("No\n");
            else printf("Yes\n");
       }
   }
    return 0;
}

HDU 1598 find the most comfortable road
题意：中文题意
思路：
一开始想了很久才想通，先把边进行排序，然后枚举边的重点和起点，但是这样就是三重循环，t了。
之后的改进，大概就是，只用枚举起点，当循环到两点联通的时候，就可以break了，这样就改进成了二重循环。
一开始就是卡在，如何判断两点联通，这里用到的主要是克鲁斯卡尔算法的思想。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int par[205];
struct node
{
    int a,b;
    int d;
} r[1005];
void init(int n)
{
    for (int i = 1;i <= n;i++)
        par[i] = i;
}
int fin(int x)
{
    if (x == par[x]) return x;
    else return par[x] = fin(par[x]);
}
void unit(int x,int y)
{
    x = fin(x);
    y = fin(y);
    if (x != y) par[x] = y;
}
bool cmp(node p,node q)
{
    return p.d < q.d;
}
int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m) != EOF)
    {
        for (int i = 0;i < m;i++)
        {
            scanf("%d%d%d",&r[i].a,&r[i].b,&r[i].d);
        }
        sort(r,r+m,cmp);
        int q;
        scanf("%d",&q);
        for (int i = 0;i < q;i++)
        {
            int st,en;
            int minn = 100000000;
            scanf("%d%d",&st,&en);
            for (int j = 0;j < m;j++)
            {
                init(n);
                bool f = 0;
                for (int k = j;k < m;k++)
                {
                    bool ff = 0;
                    unit(r[k].a,r[k].b);
                    if (fin(st) == fin(en)) ff = 1;
                    if (ff && r[k].d - r[j].d < minn)
                    {
                        minn = r[k].d - r[j].d;
                        f = 1;
                    }
                    if (f) break;
                }
            }
            if (minn == 100000000) printf("-1\n");
            else printf("%d\n",minn);
        }
    }
    return 0;
}

hdu 3926 hands in hands
题意：
有n个小朋友，他们之间手拉手，但是一只手只能拉一只手或者不拉，现在给出两个图，表示拉手关系，问这两个图是否同构。
思路：
一开始被同构难住了，后来思考发现，每一个联通分量只能是一条链或者一个简单的环，这样就比较好判断了。利用并查集统计每一个连通分量中的点，然后判断类型，判断类型的时候用度数是否为1来判断是否为链，然后将每一个连通分量先根据大小，再根据类型进行排序，最后把两个图进行一个比较即可。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int fao[10004],fat[10004],d[10004];
vector<int> g[10004],v[10004];
struct node
{
    int ty,sz;
};
node disc1[10004],disc2[10004];
void init1(int n)
{
    for (int i = 1;i <= n;i++)
    {
        fao[i] = i;
    }
}
void init2(int n)
{
    for (int i = 1;i <= n;i++)
        fat[i] = i;
}
int fin1(int x)
{
    if (x == fao[x]) return x;
    else return fao[x] = fin1(fao[x]);
}
int fin2(int x)
{
    if (x == fat[x]) return x;
    else return fat[x] = fin2(fat[x]);
}
void unit1(int x,int y)
{
    x = fin1(x);
    y = fin1(y);
    if (x != y) fao[x] = y;
}
void unit2(int x,int y)
{
    x = fin2(x);
    y = fin2(y);
    if (x != y) fat[x] = y;
}
int dfs1(int n)
{
    for (int i = 0;i < g[n].size();i++)
    {
        int t = g[n][i];
        if (d[t] == 1) return 0;
    }
    return 1;
}
int dfs2(int n)
{
    for (int i = 0;i < v[n].size();i++)
    {
        int t = v[n][i];
        if (d[t] == 1) return 0;
    }
    return 1;
}
bool cmp(node aa,node bb)
{
    if (aa.sz == bb.sz)
        return aa.ty < bb.ty;
    return aa.sz < bb.sz;
}
int main()
{
    int t;
    scanf("%d",&t);
    int cas = 0;
    while(t--)
    {
        memset(v,0,sizeof(v));
        memset(g,0,sizeof(g));
        memset(disc1,0,sizeof(disc1));
        memset(disc2,0,sizeof(disc2));
        memset(d,0,sizeof(d));
        int n,m;
        scanf("%d%d",&n,&m);
        init1(n);
        for (int i = 0;i < m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            d[x]++;
            d[y]++;
            unit1(x,y);
        }
        for (int i = 1;i <= n;i++)
        {
            g[fin1(i)].push_back(i);
        }
        int cnt1 = 0;
        for (int i = 1;i <= n;i++)
        {
            if (g[i].size() != 0)
            {
                disc1[cnt1].sz = g[i].size();
                disc1[cnt1].ty = dfs1(i);
                cnt1++;
            }
        }
        scanf("%d%d",&n,&m);
        init2(n);
        int cnt2 = 0;
        memset(d,0,sizeof(d));
        for (int i = 0;i < m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            d[x]++;d[y]++;
            unit2(x,y);
        }
        for (int i = 1;i <= n;i++)
            v[fin2(i)].push_back(i);
        for (int i = 1;i <= n;i++)
        {
            if (v[i].size() != 0)
            {
                disc2[cnt2].sz = v[i].size();
                disc2[cnt2].ty = dfs2(i);
                cnt2++;
            }
        }
        sort(disc1,disc1 + cnt1,cmp);
        sort(disc2,disc2 + cnt2,cmp);
        bool ff = 0;
        if (cnt1 != cnt2) ff = 1;
        for (int i = 0;i < cnt1;i++)
        {
            if (disc1[i].sz != disc2[i].sz) ff = 1;
            if (disc1[i].ty != disc2[i].ty) ff = 1;
        }
        if (ff) printf("Case #%d: NO\n",++cas);
        else printf("Case #%d: YES\n",++cas);
    }
    return 0;
}

hdu 3938 portal
题意：
给出一张带权图，给出q个查询，问对于每个查询可以修建多少个传送门。两个点之间可以修建传送门的条件是两点之间的最长边小于等于每次问询的l。就是从n个点中选择2个点的问题。
思路：
这题的数据有点大，最开始想出来了正确的做法，但是t了，一开始的思路是统计一共有多少个连通分量，然后用组合计数，但是复杂度达到了O(n * n)，后来看了题解。
题解的思路是离线的，先把每一个查询都输入，然后我们把每一个来连通分量看成一个点，将所有的q排序，将所有的边按照权值排序，然后q为外层循环，边为内层循环，每一次一旦出现边的权值大于q的情况，就记录下此时的边的位置，下次就从这条边开始。因为q是非递减的，所以每一次的ans都可以以前面的作为基础，进行累加。对于每一条边，当它的两个节点已经在同一连通分量中时，ans不变，因为还是在相同数量的点中选择2点，当不连通时，就把两个连通分量的大小相乘，加到ans中，这里是组合的思想，然后将两点连通，并且大小互相加。最后输出就行了。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
struct node
{
    int a,b,c;
} e[50005];
struct qu
{
    int id,nu;
    long long res;
} qq[10005];
int par[10005];
int v[10005];
void init(int n)
{
    for (int i = 1;i <= n;i++)
        par[i] = i;
    for (int i = 1;i <= n;i++)
        v[i] = 1;
}
int fin(int x)
{
    if (x == par[x]) return x;
    else return par[x] = fin(par[x]);
}
void unit(int x,int y)
{
    x = fin(x);
    y = fin(y);
    if (x != y) par[x] = y;
}
bool cmp1(node aa,node bb)
{
    return aa.c < bb.c;
}
bool cmp2(qu aa,qu bb)
{
    return aa.nu < bb.nu;
}
bool cmp3(qu aa,qu bb)
{
    return aa.id < bb.id;
}
int main()
{
    int n,m,q;
    while (scanf("%d%d%d",&n,&m,&q) != EOF)
    {
        memset(v,0,sizeof(v));
        init(n);
        for (int i = 0;i < m;i++)
        {
            scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
        }
        for (int i = 0;i < q;i++)
        {
            scanf("%d",&qq[i].nu);
            qq[i].id = i;
        }
        sort(e,e+m,cmp1);
        sort(qq,qq+q,cmp2);
        long long ans = 0;
        int mark = 0;
        for (int j = 0;j < q;j++)
        {
            int l = qq[j].nu;
            for (int i = mark;i < m;i++)
            {
                if (e[i].c <= l)
                {
                    int x = e[i].a,y = e[i].b;
                    if (fin(x) != fin(y))
                    {
                        int rt1 = fin(x),rt2 = fin(y);
                        ans += v[rt1] * v[rt2];
                        long long t1 = v[rt1],t2 = v[rt2];
                        unit(x,y);
                        v[rt2] += t1;
                        v[rt1] += t2;
                    }
                }
                else
                {
                    mark = i;
                    break;
                }
            }
            qq[j].res = ans;
        }
        sort(qq,qq+q,cmp3);
        for (int i = 0;i < q;i++)
        {
            printf("%I64d\n",qq[i].res);
        }
    }
    return 0;
}