求助10分

御·Dragon @ 2018-07-22 10:21:39

#include<bits/stdc++.h>
using namespace std;
const int MAXN=20010;
int s[MAXN];
int n,m,z,x,y,k;
int fin(int p){
    if(s[p]==0)return p;
    fin(s[p]);
}
int main(){
    cin>>n>>m; 
    for(int i=1;i<=m;i++){
        scanf("%d",&z);
        scanf("%d %d",&x,&y);
        switch(z){
            case 1:{
                s[y]=x;
                break;
            }
            case 2:{ 
                if(fin(y)==fin(x))printf("Y\n");
                else printf("N\n");
            }
        }
    }
    return 0;
}
//样例过了，但10分

by UKE自动稽 @ 2018-07-22 10:24:23

@封禁用户名f8617dda 你不觉得需要路径压缩吗？超内存了

by 御·Dragon @ 2018-07-22 10:26:45

@UKE自动机 但本渣渣不会QWQ

by UKE自动稽 @ 2018-07-22 10:27:11

@封禁用户名f8617dda 还有，你怎么没有建立并查集这一句？

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

by UKE自动稽 @ 2018-07-22 10:29:04

@封禁用户名f8617dda 对了，你怎么不看看这个讨论再做题

by 御·Dragon @ 2018-07-22 10:29:09

@UKE自动机 我是数组，父亲表示法，P的父亲就是s[p]老铁

by 御·Dragon @ 2018-07-22 10:29:44

@UKE自动机 这是我小号发的大佬，而且还是转自我的博客！

by 八声甘州 @ 2018-07-22 10:30:21

路径压缩就是```cpp s[p]=fin(s[p])

by 御·Dragon @ 2018-07-22 10:32:12

@CONILLION What？

by 御·Dragon @ 2018-07-22 10:32:28

@CONILLION 谢大佬！

by UKE自动稽 @ 2018-07-22 10:33:14

@封禁用户名f8617dda 路径压缩是这个（这是从我的代码里节选的）

int find1(int o) {
    if (f[o]==o) return o;
    else return f[o]=find1(f[o]);
}