[并查集] hihocoder 1158 质数相关

题目大意

题目链接，定义两个数\(a,b\)质数相关满足 \(b=a\times p\), 且\(p\)是质数。给定数组，问最大质数无关子集大小。

算法思路

首先想到的是将每个数看作一个顶点，质数相关的两个数之间连边，求最大独立子集。但是最大独立子集复杂度很高，发现这个图中不存在环！可以说明如下\(b=p_1 \times a, c=p_2 \times a\)，那么 \(b,c\)一定质数无关，其他情形也可以类似说明。

于是问题转化为树上的最大独立子集，若将根节点深度设为0，遍历得到每个节点的深度值，则最大独立子集大小为 深度值为奇数的节点数 或者 深度值为偶数的节点数。考虑到题目中边很容易确定，但是树结构不容易建立，并且只需要区分两类节点，因而使用并查集维护。

并查集可以同时维护父节点和与父节点的关系，这里我们用0表示深度奇偶性相同，1表示奇偶性不同。最后累计每棵两类节点数，取最大值即可。详见代码如下。

算法代码

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

const int MM = 500005;
bool prime[500005] = { false, true, true };

int data[1005];
int n;

int parent[1005];
int r[1005]; 
int ans[1005][2];

void uf(int a, int b, int t)
{
    if (parent[a] == a) {
        parent[a] = b;
        r[a] = t;
        return;
    }
    uf(parent[a], b, (t+r[a])%2);
    parent[a] = b;
    r[a] = t;
    return;
}

int main()
{
    for (int i = 3; i < MM; i++)
        prime[i] = true;
    for (int i = 2; i < MM; i++) {
        if (prime[i]) {
            for (int j = 2; j*i < MM;j++)
                prime[j*i] = false;
        }
    }

    int t;
    scanf("%d", &t);
    for(int tt=1;tt<=t;tt++) {

        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", data + i);
        }
        sort(data, data + n);

        memset(r, 0, sizeof(r));
        for (int i = 0; i < n; i++)
            parent[i] = i;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (data[j] % data[i] == 0 && prime[(data[j] / data[i])]) {
                    // merge i, j
                    int pi = parent[i];
                    int pj = parent[j], rj = r[j];

                    while (pi != parent[pi]) {
                        pi = parent[pi];
                    }
                    while (pj != parent[pj]) {
                        rj+=r[pj];
                        pj = parent[pj];
                    }

                    uf(i, pj, (1 + rj) % 2);

                }
            }
        }

        memset(ans, 0, sizeof(ans));

        for (int i = 0; i < n; i++) {
            int pi = parent[i], ri = r[i];
            while (pi != parent[pi]) {
                ri+=r[pi];
                pi = parent[pi];
            }

            ans[pi][ri % 2]++;
        }

        int a = 0;
        for (int i = 0; i < n; i++) {
            a += max(ans[i][0], ans[i][1]);
        }

        printf("Case #%d: %d\n", tt, a);
    }
    return 0;
}