第二组输入不让下载，但是re了，求助

心对心天 @ 2019-03-23 20:15:44

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

int a[100];int zi; 

int find(int x)
{
    if (a[x]==0)
    return x;
    else
    {
        a[x]=find(a[x]);
        return a[x];
    }

}

void he(int x,int y)
{
    int q,b;
    q=find(x);
    //printf("<%d>",q);
    b=find(y);
    //printf("<%d>\n",b);
    if(q!=b)
    a[q]=b;

}

char chazhao(int x,int y)
{
    if(find(x)==find(y))
    return 'Y';
    else
    return 'N';
}

int main(){
    int n,m,q,b;

    //cin>>n>>m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&zi,&q,&b);
        if(zi==1)
        he(q,b);
        else
        {
        printf("%c",chazhao(q,b));
        cout<<endl;
        }
    }
    return 0;
}

by Eason_AC @ 2019-03-23 20:21:13

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 10005
using namespace std;

int father[N];
inline int fa(int x) {
    if(father[x] != x)  father[x] = fa(father[x]);
    return father[x];
}
inline void unionn(int x, int y) {
    x = fa(x), y = fa(y);
    if(x == y)  return;
    father[y] = x;
    return;
}
inline bool same(int x, int y) {
    return fa(x) == fa(y);
}

int n, m;

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        father[i] = i;
    for(int i = 1; i <= m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if(a == 1)  unionn(b, c);
        else if(a == 2) {
            if(same(b, c))
                printf("Y\n");
            else
                printf("N\n");
        }
    }
    return 0;
} 

看一下我的吧

by t162 @ 2019-03-23 20:23:37

if(a[x]==0)

by Eason_AC @ 2019-03-23 20:24:32

1、路径压缩

int find(int x)
{
    if (a[x]==0)
    return x;
    else
    {
        a[x]=find(a[x]);
        return a[x];
    }
}

改为

inline int fa(int x) {
    if(father[x] != x)  father[x] = fa(father[x]);
    return father[x];
}

2、合并不用这么复杂，直接复制就行。

void he(int x,int y)
{
    int q,b;
    q=find(x);
    //printf("<%d>",q);
    b=find(y);
    //printf("<%d>\n",b);
    if(q!=b)
    a[q]=b;
}

改为

inline void unionn(int x, int y) {
    x = fa(x), y = fa(y);
    if(x == y)  return;
    father[y] = x;
    return;
}

by Eason_AC @ 2019-03-23 20:27:04

3、注意预处理

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

by Eason_AC @ 2019-03-23 20:27:26

我就是没预处理，也是70分

by LCuter @ 2019-03-23 20:27:40

@心对心天 数组开小了

by Eason_AC @ 2019-03-23 20:30:01

@常暗踏阴 是的，起码要开到10000

by 心对心天 @ 2019-03-23 20:53:03

谢谢各位了，我知道了