自己已经检查了数遍 , 无论从逻辑上 和 代码实现上都找不出错误 。 已经将思路等进行了注释 , 求大佬帮忙查查错 。
#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;
}
阿里嘎多