/ Vijos / 讨论 / 家族 /

这么裸的并查集哪里有问题了,和大家写的都一样啊……

#include <iostream>
using namespace std;

int n, m, p;
int root[5001];

int Find(int x)
{
    if(root[x] != x)
        root[x] = Find(root[x]);
    return root[x];
}
void Union(int x, int y)
{
    int xRoot = root[x];
    int yRoot = root[y];
    if(xRoot != yRoot){
        root[xRoot] = yRoot;
    }
    return;
}

int main()
{
    cin >> n >> m >> p;
    for(int i = 1; i <= n; i++)
        root[i] = i;
    int tx, ty;
    for(int i = 1; i <= m; i++) {
        cin >> tx >> ty;
        Union(tx, ty);
    }
    for(int i = 1; i <= p; i++) {
        cin >> tx >> ty;
        if (Find(tx) == Find(ty))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 576 KiB, score = 10
测试数据 #3: RuntimeError, time = 0 ms, mem = 2600 KiB, score = 0
测试数据 #4: WrongAnswer, time = 15 ms, mem = 576 KiB, score = 0
测试数据 #5: RuntimeError, time = 15 ms, mem = 2604 KiB, score = 0
测试数据 #6: RuntimeError, time = 15 ms, mem = 2608 KiB, score = 0
测试数据 #7: WrongAnswer, time = 62 ms, mem = 580 KiB, score = 0
测试数据 #8: WrongAnswer, time = 62 ms, mem = 584 KiB, score = 0
测试数据 #9: WrongAnswer, time = 62 ms, mem = 576 KiB, score = 0

2 条评论

  • @ 2016-09-05 13:16:50

    ###****是```,不是···****

  • @ 2016-07-16 21:52:11

    UnionxRootyRoot未必是xy所在集合的根节点,需要用Find函数来找出这个根节点。
    另外在输入`这个字符时,应当使用英文输入法和半角字符。
    最后,请善用预览和修改功能。

    • @ 2016-09-05 23:19:47

      抱歉好一段时间没上,才看到,是我脑残了= = 不过谢谢啦!

  • 1

信息

ID
1034
难度
4
分类
数据结构 | 并查集 点击显示
标签
(无)
递交数
9379
已通过
3848
通过率
41%
被复制
16
上传者