L2-016 愿天下有情人都是失散多年的兄妹 题解

L2-016 愿天下有情人都是失散多年的兄妹

链接：题目详情 - L2-016 愿天下有情人都是失散多年的兄妹 (pintia.cn)

思路：刚开始想用并查集，后来改用DFS，但确切来说只是用了它的一个简单的搜索功能。

先说最后卡住的点，题给测试数据中可能有老一辈的人，所以输入父母数据时，需要对父母Id增加性别信息记录，加了这个处理后，直接就通过了。

刚开始用了结构体数组，后来发现用不上，删了。可以用pair或者map写写试试。

#include<cstdio>
const int N=100005;
int n,m,dai,a,b,c;
bool wudai[N]={false};
char sexa[N];
int father[N],mother[N];
void init(){
    for(int i=0;i<N;i++){
        father[i]=-1;
        mother[i]=-1;
    }
}
void DFS(int x){
    if(dai==5){
        return;
    }
    dai++;
    wudai[x]=true;
    a=father[x];
    if(a!=-1){
        DFS(a);
    }
    b=mother[x];
    if(b!=-1){
        DFS(b);
    }
    dai--;
}
void DFS1(int x){
    if(dai==5){
        return;
    }
    dai++;
    if(wudai[x])
        c=1;
    a=father[x];
    if(a!=-1){
        DFS1(a);
    }
    b=mother[x];
    if(b!=-1){
        DFS1(b);
    }
    dai--;
}
int main(){
    int i,x,y,a,b,l,v,e;
    char o;
    init();
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %c %d %d",&l,&o,&v,&e);
        if(v!=-1){
            father[l]=v;
            sexa[v]='M';
        }
        if(e!=-1){
            mother[l]=e;
            sexa[e]='F';
        }
        sexa[l]=o;
    }
    scanf("%d",&m);
    for(i=0;i<m;i++){
        scanf("%d %d",&x,&y);
        for(int j=0;j<N;j++){
            wudai[j]=false;
        }
        if(sexa[x]==sexa[y])
            printf("Never Mind\n");
        else{
            dai=0;
            DFS(x);
            c=0;
            dai=0;
            DFS1(y);
            if(c==1){
                printf("No\n");
            }
            else
                printf("Yes\n");
        }
    }
    return 0;
}