HDU_1856_More is better

2011-05-15  来源:本站原创  分类:CPP  人气:83 

http://acm.hdu.edu.cn/showproblem.php?pid=1856

And the set of simple questions intended to check: given the same set of two elements, the most for the last set of elements that the number of elements, note that each element can exist independently, so that at least one

#include <iostream>
using namespace std;

int pre[10000005], con[10000005];

int find (int a)
{
    int b = a;
    while (a != pre[a])
        a = pre[a];
    while (b != a)
    {
        int t = b;
        b = pre[b];
        pre[t] = a;
    }
    return a;
}
int main()
{
    int n, i, a, b, A, B, res;
    while (scanf ("%d", &n) != EOF)
    {
        res = 1;    // Here init must be 1, because the merge operation may not execute , Moreover, each collection has at least 1 person
        for (i = 1; i <= 10000000; i++)
            pre[i] = i, con[i] = 1;
        for (i = 0; i < n; i++)
        {
            scanf ("%d%d", &a, &b);
            A = find (a);
            B = find (b);
            if (A != B)
            {
                pre[B] = A;
                con[A] += con[B];
                if (res < con[A])
                    res = con[A];
            }
        }
        printf ("%d\n", res);
    }
    return 0;
}
相关文章
  • HDU_1856_More is better 2011-05-15

    http://acm.hdu.edu.cn/showproblem.php?pid=1856 And the set of simple questions intended to check: given the same set of two elements, the most for the last set of elements that the number of elements, note that each element can exist independently, s