学步园

之所以把这两题放一块看是因为寻找祖先结点是有区别的，不然一个爆栈，一个TLE

hdu1272 小希的迷宫

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int root[100001],foot[100001];
int find(int t){   //不能用递归寻找祖先借点，不然会爆栈，汗
    while(root[t]!=t)
        t=root[t];
    return root[t];
}
void check(int a,int b){
    foot[a]=foot[b]=1;
    int ra=find(a);
    int rb=find(b);
    if(ra!=rb)
        root[ra]=rb;
}
void reset(){   //初始化
    for(int i=1;i<=100000;i++)
        root[i]=i;
    memset(foot,0,sizeof(foot));
}
int main(){
    int i=1;
    bool flag=0;
    int a,b;
    int key=0;
    reset();
    while(scanf("%d%d",&a,&b)){   //输入的格式也很奇葩
        if(a==-1&&b==-1)
            break;
        if(a==0&&b==0){
            for(i=1;i<=100000;i++)
                if(root[i]==i&&foot[i]==1)   //foot[]==1代表输入文件中包含的点
                    key++;
            if(key>1)
                flag=1;
            if(flag)
                printf("No\n");
            else
                printf("Yes\n");
            flag=0;
            key=0;
            reset();
            continue;
        }
        if(find(a)==find(b))
            flag=1;
        else
            check(a,b);
    }
    return 0;
}

hdu1856 More is better

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int root[10000010],sign[10000010];
int find(int c){   //亲测若采用while()找祖先直接TLE
    if(root[c]!=c)
        root[c]=find(root[c]);
    return root[c];
}
void check(int a,int b){
    int ra=find(a);
    int rb=find(b);
    if(ra!=rb){
        root[ra]=rb;
        sign[rb]+=sign[ra];
    }
}
int main(){
    int m;
    int i;
    int b1,b2;
    while(scanf("%d",&m)!=EOF){
        for(i=1;i<=10000000;i++){
            root[i]=i;
            sign[i]=1;
        }
        for(i=1;i<=m;i++){
            scanf("%d%d",&b1,&b2);
            check(b1,b2);
        }
        int ans=0;
        for(i=1;i<=10000000;i++)
            if(sign[i]>ans)
                ans=sign[i];
        printf("%d\n",ans);
    }
    return 0;
}

我已经感觉到蛋疼了...