三十分 七个点WA（TOO MANG OR TOO FEW LINES） 求解

P3367 【模板】并查集

KingKrush @ 2018-08-08 19:34:01

#include <bits/stdc++.h>
using namespace std;
int pre[10005];
int a[100000] ;
int find(int x)
{
    int r=x;
    while(pre[r]!=r)
    r=pre[r];
    int i=x,j;
    while(i!=r)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}

void join(int x,int y)
{
    int a=find(x);//x的根节点为a
    int b=find(y);//y的根节点为b
    if(a!=b)//如果a,b不是相同的根节点，则说明ab不是连通的
    {
        pre[a]=b;
    }
}

int pan(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b)
    return 1;
    else if(a!=b)
    return 2;
}

int main()
{
    int n,m,x,y,z,bo=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    pre[i]=i;
    for(int g=1;g<=m;g++)
    {
        scanf("%d%d%d",&z,&x,&y);
        if(z==1)
        join(x,y);
        if(z==2)
        {
        a[bo]=pan(x,y);
        bo++;

    }
}
    for(int x=1;x<=n+1;x++)
    {
        if(a[x]==1)
        printf("%c\n",89);
        else if(a[x]==2)
        printf("%c\n",78);
    }
    return 0;
}

有一点绝望

by 二中胡剑锋 @ 2018-08-12 12:00:39

在你的基础上修改的，注释掉一些内容

include <bits/stdc++.h>

using namespace std; int pre[10005]; int a[100000] ; int find(int x) { // int r=x; // while(pre[r]!=r) // r=pre[r]; // int i=x,j; // while(i!=r) { // j=pre[i]; // pre[i]=r; // i=j; // } // return r; if(pre[x]==x) return x; return pre[x]=find(pre[x]);//压缩路径 }

void join(int x,int y) { int a=find(x);//x的根节点为a int b=find(y);//y的根节点为b if(a!=b) { //如果a,b不是相同的根节点，则说明ab不是连通的 pre[a]=b; } return; } //int 空函数无返回值 void pan(int x,int y) { //判断是否为“亲戚” int a=find(x); int b=find(y); if(a==b) printf("Y\n"); else printf("N\n");//直接输出 } int main() { int n,m,x,y,z; scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) pre[i]=i;//初始化 for (int i=1; i<=m; i++) { scanf("%d %d %d",&z,&x,&y); if (z==1) join(x,y);//可以直接调用函数 else pan(x,y); } return 0; }

|