全WA了,求大佬帮忙康康
查看原帖
全WA了,求大佬帮忙康康
1121620
LazyAndCreepy楼主2024/1/24 11:03

自己已经检查了数遍 , 无论从逻辑上 和 代码实现上都找不出错误 。 已经将思路等进行了注释 , 求大佬帮忙查查错 。

#include<stdio.h>
#include<string.h>
#include<stdbool.h>

#define MAXSIZE 50000

//并查集查找函数 , 返回父节点
int find(int i , int *f){
    if(f[i] == i)
        return i;
    return f[i] = find(f[i] , f);
}

//并查集判断函数 , 返回判断结果
bool judge(int x , int y , int *f){
    x = find(x , f) ; y = find(y , f);
    return x==y ? true : false;
}

//并查集合并函数
void add(int x , int y , int *f){
    f[find(x , f)] = find(y , f);
    return ;
}

//并查集初始化函数
void Ini(int *f){
    int i;
    for(i=0 ; i<MAXSIZE ; i++) f[i] = i;
    return ;
}

//储存出现过的所有名字 , 不储存重复的名字 , 可以通过序号找到相对应的名字
//同时 , 序号为 0 的空间作为暂存缓冲区 , 先将读取到的字符串存入其中 , 再
//进行后续操作 
struct{char name[50] ;}qwq[20005] = {0};

typedef struct{int ptr , l , r ; bool exit;}tree;

//搜索树结构,用于优化查找过程
tree T[50005] = {0};
int size=2; //T的末尾元素的下标 , 从 2 开始而不是从 0 开始有特殊考虑

//二叉树结构,在字符串集中插入指定字符串 ,同时按照字典序将字符串排成升序结构
int inser(void){
    int ptr = 1;
    //序号 1 定义为根结点 , 0 定义为空结点
    while(T[ptr].exit){
        //比较根节点所指向字符 与 待查找字符的大小关系
        if( strcmp( qwq[ T->ptr ].name , qwq[ ptr ].name ) > 0 ){
            if(T[T[ptr].l].exit){
                ptr = T[ptr].l;
            }
            else{
                ptr = T[ptr].l = size;
                size++;
            }
        }else if( strcmp( qwq[ T->ptr ].name , qwq[ ptr ].name ) < 0 ){
            if(T[T[ptr].r].exit){
                ptr = T[ptr].r;
            }else{
                ptr = T[ptr].r = size;
                size++;
            }
        }else{
            return ptr;
            //如果当前字符串 与 已经存储的字符串 重复,则返回重复的字符串 的储存序号
        }
    }
    T[ptr].ptr = ptr;
    strcpy( qwq[ptr].name , qwq[0].name );

    T[ptr].exit = true; //将当前结点的状态改为非空 ,左右子节点指向空
    T[ptr].l = 0;
    T[ptr].r = 0;

    return ptr;
}

int main(void){

    int f[MAXSIZE];
    Ini(f);
    
    int n , m , k;
    int i ;

    scanf("%d %d",&n,&m);

    for(i=1 ; i<=n ; i++){
        scanf("%s", qwq[0].name);
        inser();  //将读取到的字符串储存起来
    }

    char temp[7]; //要一次性读取两个字符串 , 而前面定义的函数均一次只能处理一个字符 , 故新增加一个缓存区
    int a , b;    //a , b 暂存查找到的字符串对应的序号

    for(i=1 ; i<=m ; i++){
        scanf("%s %s", qwq[0].name , temp);
        //因为名字是重复出现过的字符串 , 所以刚刚的插入函数也可以充当查找函数的使用
        //找到名字对应的序号后 , 再将各自的序号在并查集种合并

        a = inser();
        strcpy( qwq[0].name , temp );
        b = inser();
        add(a , b , f);
    }

    scanf("%d",&k);
    for(i=1 ; i<=k ; i++){
        scanf("%s %s", qwq[0].name , temp);
        //同样通过插入函数去找到名字对应的序号 , 再通过并查集进行查找

        //就算名字没有出现过也没关系 ,插入函数会新增加一个结点进行储存并返回其序号 , 该序号由于没出现过
        //在并查集中其父节点一定是自己 , 不影响判断结果 , 只需考虑如果无效名字询问过多 , T数组是否有足
        //够空间容纳即可 ,应该不至于几百万次询问都是无效名字吧 , 那这体育老师可以解雇了233

        //考虑到如果询问的名字未曾出现过 , 且询问的是 自身 和 自身 是否在同一组 , 由于题目未定义该类情
        //况 , 故从逻辑上考虑 , 应该可以认为是一组 。 
        a = inser();
        strcpy(qwq[0].name , temp);
        b = inser();
        if( judge(a , b , f) ){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }

    return 0;
}

阿里嘎多

2024/1/24 11:03
加载中...