学步园

题目

判断是否有两个点的祖先已经是同一个了。

判断是否联通。

学了一句代码来防爆栈

#include<iostream>
#include<cstdio>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define maxn 100005

int pre[maxn];
bool flag,vis[maxn];

int find(int x)
{
   return pre[x]==x?x:(pre[x]=find(pre[x]));
}

void Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a!=b) pre[a]=b;
    else flag=false;
}

int main()
{
    int n,m,i,j;
    while(cin>>n>>m){
        if(n==-1&&m==-1) break;
        if(n==0){
            puts("Yes");
            continue;
        }
        for(i=0;i<maxn;i++){
          pre[i]=i;
          vis[i]=false;
        }
       vis[n]=vis[m]=true;
       flag=true;
       Union(n,m);
       while(cin>>n>>m,n+m){
           Union(n,m);
           vis[n]=true;vis[m]=true;

       }
        int ans=0;
        for(i=0;i<maxn;i++){
          if(pre[i]==i&&vis[i]) ans++;
          if(ans>1) flag=false;
        }
        puts(flag?"Yes":"No");
    }
    return 0;
}