小希的迷宫_hdu_1272

#include <stdio.h>
#include <stdlib.h>
int map[100010];
void init(){
    int i;
    for(i=1;i<=100000;i++){
        map[i]=i;
    }
}
int getboss(int p){
    if(map[p]==p){
        return p;
    }
    else{
        map[p]=getboss(map[p]);
        return map[p];
    }
}
void merge(int p,int q){
    int t1=getboss(p),t2=getboss(q);
    if(t1!=t2){
        map[t2]=t1;
    }
}
int main(){
    int n=0,m=0,flag=0,i,max=0,rec=0,flag1=0;
    init();
    while(1){
        scanf("%d%d",&n,&m);
        if(n>max){
            max=n;
        }
        if(m>max){
            max=m;
        }
        if(n==m&&n==-1){
            break;
        }
        if(n==m&&n==0){
            if(flag==0){
                for(i=1;i<=max;i++){
                    int temp=getboss(i);
                    if(temp!=i){
                        if(flag1==0){
                            rec=temp;
                            flag1=1;
                        }
                        if(temp!=rec){
                            printf("Non");
                            flag=1;
                            break;
                        }
                    }
                }
                if(flag==0){
                    printf("Yesn");
                }
            }
            else{
                printf("Non");
            }
            init();
            flag=0;
            flag1=0;
            continue;
        }
        if(getboss(m)==n||getboss(n)==m){
            flag=1;
        }
        merge(n, m);
    }
    return 0;
}

这个题是并查集变形,只要找输入的两个数是否有关系即可,不要忘了判断每个点都是联通的!!! 就是因为这个错了好几次😂