POJ 1308 Is It A Tree?

       题意是判断这是不是一棵树，条件就是不能有环，而且只能有一个根节点，和小希的迷宫哪道题差不多，可以看下判断有没有环的详解传送门，这道题呢需要加一个改动的地方就是因为不知道这个树的大小，可能不是从1开始的，也不知道是从多少结束的，所以刚开始要把最大值和最小值记录下来。

AC代码：

代码语言：javascript复制

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 100005;
int pre[MAXN];
int vis[MAXN];
int Max = -1;
int Min = 0x3f3f3f3f;
int flag;

void init(){
  for(int i=0;i<=MAXN;i  ){
    pre[i] = i;
    vis[i] = 0;
  }
}

int Find(int x){
  if (x != pre[x]){
    pre[x] = Find(pre[x]);
  }
  return pre[x];
}

void merge(int x,int y){
  int fx = Find(x);
  int fy = Find(y);
  if(fx != fy){
    pre[fy] = fx;
  }
  else{
    flag = 0;
  }
}

int main()
{
  int n,m;
  int Case = 1;
  while(~scanf("%d%d",&n,&m)){
    if(n==0&&m==0){
      printf("Case %d is a tree.n",Case  );
      continue;
    }
    if(n==-1&&m==-1)break;
    init();
    flag = 1;
    merge(n,m);
    vis[n] = 1;
    vis[m] = 1;
    while(cin>>n>>m){
      if(n==0&&m==0)break;
      if(n>Max) Max = n;             // 因为不知道树的大小，需要计算最大值和最小值进行查找
      if(m>Max) Max = m;
      if(n<Min) Min = n;
      if(m<Min) Min = m;
      merge(n,m);
      vis[n] = 1;
      vis[m] = 1;
    }
      if(flag == 0){
        cout<<"Case "<<Case  <<" is not a tree."<<endl;
      }
      else{
        int sum = 0;
        for(int i=Min;i<=Max;i  ){
          if(pre[i]==i&&vis[i]==1){
            sum  ;
          }
        }
        if(sum==1)
        cout<<"Case "<<Case  <<" is a tree."<<endl;
        else
        cout<<"Case "<<Case  <<" is not a tree."<<endl;
    }
  }
  return 0;
}

it

0 人点赞