跪了,查了一下午没查出来为什么有三个RE

P3367 【模板】并查集

_H1kar1 @ 2019-03-30 15:49:42

注释掉的是测试过程 数组开比正解还大,应该不是这个问题,,, re了2,9,10三个点


#include<iostream>
using namespace std;
int n,m;
int tr[10020]={0};

int findhead(int p){
    //system("pause");
    if(tr[p]==p)    return p;//it's head itself
    return tr[p]=findhead(tr[p]);    //在这里压缩路径 
}

/*
void unite(int a,int b){
    //if(findhead(a)==findhead(b))  return ;//他们在一棵树上 
    tr[findhead(b)]=findhead(a);
}
*/

int main(){

    cin>>n>>m;

    for(int i=1;i<=m;i++)//reset
        tr[i]=i;

    int zi,xi,yi;
    for(int i=1;i<=m;i++){
        cin>>zi>>xi>>yi;
        if(zi==1){
            tr[findhead(xi)]=findhead(yi);
        }
        else
            if(findhead(xi)==findhead(yi))
                cout<<'Y'<<endl;
            else    cout<<'N'<<endl;
        ///////////////////////////////////////////////////
        //cout<<"*****"<<endl;
        //cout<<"findheadxi="<<findhead(xi)<<endl
        //  <<"findheadyi="<<findhead(yi)<<endl;
        //for(int i=1;i<=m;i++)
        //  cout<<tr[i]<<' ';
        //cout<<endl<<"*****"<<endl;
    }
    return 0;
} 

谢谢指点了,真的难受


by Celestial_Scarlet @ 2019-03-30 15:54:13

@迪奥·布朗度 初始化炸了,是1~n


by Eason_AC @ 2019-03-30 15:54:42

for(int i=1;i<=m;i++)
        tr[i]=i;

改成

for(int i=1;i<=n;i++)
        tr[i]=i;

就可以了吧


by namespace_std @ 2019-03-30 15:55:12

m是2e5,n是1e4

然而你初始化的时候将1,...,m都初始化了啊

    for(int i=1;i<=m;i++)//reset
                   ^

by Hexarhy @ 2019-03-30 15:55:28

for(int i=1;i<=m;i++)//reset
        tr[i]=i;

不太对,应该是i<=n


by Eason_AC @ 2019-03-30 15:55:39

楼上三个正解(逃


by _H1kar1 @ 2019-03-30 16:06:31

@HyyypRtf06 谢谢,终于A了,我第一次打并查集,一下午都在查并查集的基本操作上,哪能想到手滑打的初始化错了(汗)


by _H1kar1 @ 2019-03-30 16:06:37

@baoyu 谢谢,终于A了,我第一次打并查集,一下午都在查并查集的基本操作上,哪能想到手滑打的初始化错了(汗)


by _H1kar1 @ 2019-03-30 16:06:49

@Eason_AC 谢谢,终于A了,我第一次打并查集,一下午都在查并查集的基本操作上,哪能想到手滑打的初始化错了(汗)


by _H1kar1 @ 2019-03-30 16:07:07

@namespace_std 谢谢,终于A了,我第一次打并查集,一下午都在查并查集的基本操作上,哪能想到手滑打的初始化错了(汗)


by _H1kar1 @ 2019-03-30 16:07:39

突然想到我应该一次把人都at完的(扶额)


|