区分这两者:单个元素的统计量(转移次数),整个集合的统计量(元素个数)。

细节:龙珠不可能被转移到它以前存在过的地方,那里已经没有龙珠了(T A B:B所在的城市必须有龙珠)。

/*328ms,368KB*/

int fa[mx], rk[mx], city[mx];

int find(int x)
{
    int tmp = fa[x];
    if (~tmp)
    {
        fa[x] = find(tmp);
        rk[x] += rk[tmp]; ///rk是单个元素的转移次数
     return fa[x];
    }
    return x;
}

int main()
{
    int T, t, N, Q, x, y, fax;
    RI(T);
    Forr(t, 1, T + 1)
    {
        RII(N, Q);
        mem(fa, -1), mem(rk, 0), fill(city + 1, city + N + 1, 1);
        printf("Case %d:\n", t);
        while (Q--)
        {
            getchar();
            if (getchar() == 'T')
            {
                RII(x, y);
                x = find(x), y = find(y);
                if (x != y)
                {
                    fa[x] = y;
                    city[y] += city[x]; ///更新集合元素个数
                 ++rk[x];
                }
            }
            else
            {
                RI(x), fax = find(x);
                PIII(fax, city[fax], rk[x]);
            }
        }
    }
    return 0;
}

Comments

comments powered by Disqus