大佬帮忙看下 为什么全MLE啊

P3367 【模板】并查集

张小花 @ 2019-08-22 20:54:41

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 10010;

struct Node
{
    int father, size;
};

Node trees[MAX_N];
int n, m;
int x, y, z, x_root, y_root;

int find_root(int index)
{
    if (trees[index].father == -1)
    {
        return index;
    }
    int root = find_root(trees[index].father);
    trees[index].father = root;
    return root;
}

void merge(int root1, int root2)
{
    if (trees[root1].size < trees[root2].size)
    {
        trees[root1].father = root2;
        trees[root2].size += trees[root1].size;
    }
    else
    {
        trees[root2].father = root1;
        trees[root1].size += trees[root2].size;
    }
}

int main()
{
    cin >> n >> m;
    Node node;
    node.size = 1;
    node.father = -1;
    for (int i = 1; i <= n; i++)
    {
        trees[i] = node;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> z >> x >> y;
        x_root = find_root(x);
        y_root = find_root(y);
        if (z == 1)
        {
            merge(x_root, y_root);
        } 
        else
        {
            if (x_root == y_root)
            {
                cout << "Y" << endl;
            }
            else
            {
                cout << "N" << endl;
            }
        }
    }
    return 0;
}

by 张小花 @ 2019-08-22 21:08:06

@Null_Cat 开了size就MLE是什么鬼 by the way 数据大不开size会TLE qwq


by longlongzhu123 @ 2019-08-22 21:10:29

@张小花 找到问题了:

问题出在 merge 函数里,数据有合并两个原本在同一集合里的元素的操作

修改后代码:

void merge(int root1, int root2)
{
    if (root1 == root2) return;
    if (trees[root1].size < trees[root2].size)
    {
        trees[root1].father = root2;
        trees[root2].size += trees[root1].size;
    }
    else
    {
        trees[root2].father = root1;
        trees[root1].size += trees[root2].size;
    }
}

实测 AC


by 张小花 @ 2019-08-22 21:11:00

表示我用这个并查集A了 P1306


by longlongzhu123 @ 2019-08-22 21:11:09

MLE 应该是 find_root 会死循环,然后递归爆栈


by 张小花 @ 2019-08-22 21:11:40

@longlongzhu123 嗯哼 谢谢大佬


by Vomedakth @ 2019-08-22 21:11:59

@张小花

不加按秩合并不会影响太多时间复杂度,反正我没见过卡这个的


by 张小花 @ 2019-08-22 21:12:41

哦 突然发现我之前写了这句话。。 尴尬


by wkywkywky @ 2019-08-22 21:17:53

@张小花

merge(x_root, y_root);

可能把相同的两个元素合并起来,使tree[x].father=x

导致find_root

 if (trees[index].father == -1)

永远无法成立,爆栈了


上一页 |