本文共 1736 字，大约阅读时间需要 5 分钟。

并查集的理论介绍可以参考

/*poj 1611题目大意：0号学生感染了，和他一组的人也会感染，然后这些人在所在的其他组的人也会感染。那么现在求被感染的总人数。多组输入：第一行为学生数，组数接下来的每一组中第一个为学生的个数，后面为学生序号输出：计算被感染的总人数解题思路：并查集。用一个数组nums表示每一组中的人数，对每一组的人合并，并计算nums[0]即为被感染总数*/#include 
   
    #define LOCAL#ifdef LOCAL#include 
    
     #endifusing namespace std;const int MAXN = 30001;     //节点数int parent[MAXN];           //父节点int ran[MAXN];              //树的高度int num[MAXN];              //元素的个数//初始化void MakeSet(int x){    parent[x] = x;    ran[x] = 0;    num[x] = 1;}//查找int FindSet(int x){    int r = x, tmp;    while (parent[r] != r)  //找到根节点        r = parent[r];    //路径压缩    while (x != r)    {        tmp = parent[x];        parent[x] = r;        x = tmp;    }    return x;}//合并void UnionSet(int x, int y){    x = FindSet(x);    y = FindSet(y);    if (x == y)         //有相同的根节点，不用合并啦        return;    if (ran[x] > ran[y])    {        parent[y] = x;  //x所在的树高度比y高，让x成为y的根节点        num[x] += num[y];    }    else    {        parent[x] = y;        if (ran[x] == ran[y])            ran[y]++;        num[y] += num[x];    }}int main(){#ifdef LOCAL    FILE* s;    if (freopen_s(&s, "poj1611.txt", "r", stdin) != 0)    {        cout << "Open file error!" << endl;        return -1;    }#endif    int n, m, x, y, i, t, j;    while (cin >> n >> m && (m || n))    {        if (m == 0)        {            cout << 1 << endl;            continue;        }        for (i = 0; i < n; ++i)            MakeSet(i);        for (i = 0; i < m; ++i)        {            cin >> t >> x;            for (j = 1; j < t; ++j)            {                cin >> y;                UnionSet(x, y);                x = y;            }        }        x = FindSet(0);        cout << num[x] << endl;    }#ifdef LOCAL    fclose(s);#endif    return 0;}
    
   

转载地址：http://mmmxb.baihongyu.com/