70分求助

P3367 【模板】并查集

qfpjm @ 2021-03-07 22:15:01

#include<bits/stdc++.h>

using namespace std;

const int len = 1000001;
int parent[len] = {0};
int n, m; 

void union_(int v1, int v2){
    int p1 = parent[v1];
    int p2 = parent[v2];
    if (p1 != p2)
    {
        for (int i = 0;i < len;i ++)
        {
            if (parent[i] == p1)
            {
                parent[i] = p2;
            }
        }
    }
}

int find(int v1)
{
    return parent[v1];
}

bool isSame(int v1, int v2)
{
    return find(v1) == find(v2);
}

int main()
{
    // 初始化, 所有的元素分别属于不同的集合
    for (int i = 0; i < len; i++){
        parent[i] = i;
    }
    cin >> n >> m;
    for (int i = 1;i <= m;i ++)
    {
        int z, x, y;
        scanf("%d%d%d", &z, &x, &y);
        if (z == 1)
        {
            union_(x, y);
        } 
        else
        {
            if (isSame(x, y))
            {
                printf("Y\n");
            }
            else
            {
                printf("N\n");
            }
        }
    }
    return 0;
}

by qfpjm @ 2021-03-07 22:16:02


by xfrvq @ 2021-03-07 22:18:04

神奇的写法


by xfrvq @ 2021-03-07 22:18:41


by xfrvq @ 2021-03-07 22:20:10

1e4再乘上1e5会爆


by CGDGAD @ 2021-03-07 22:20:27

union 这个写法太奇怪了,看一下题解吧


by CGDGAD @ 2021-03-07 22:22:05

void union_(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 != p2)
    {
        f[v1] = p2;
    }
}

感觉这个才对


by 可持久化CRTrie @ 2021-03-07 23:24:53

合并时更新的话应该和暴力差不多


by 可持久化CRTrie @ 2021-03-07 23:29:10

没有体现出并查集的优势


|