首页 > 代码库 > POJ1308

POJ1308

1、题目链接地址

  http://poj.org/problem?id=1308

2、源代码

#include<iostream>using namespace std;#define MAXN 100int set[MAXN]; //set[]记录每个节点的父节点int FindSet(int x) //寻找x所在根的根节点{     if(set[x]==x)         return x;     if(set[x]==-x)         return -x;     else         set[x]=FindSet(set[x]);     return set[x];}int main(){     int pointa,pointb,FSa,FSb;     int cas=1,num=0,I;     bool judge=0,flag=0;//judge为是否判断完,flag为是否有边输入     for(I=0;I<MAXN;I++)         set[I]=-I;     while(cin>>pointa>>pointb,pointa>=0)     {         if(pointa==0)         {                  if(num==1||flag==0)                       cout<<"Case "<<cas<<" is a tree.\n";                   else                       cout<<"Case "<<cas<<" is not a tree.\n";                   cas++;                   flag=0;                   num=0;                   judge=0;                   for(I=0;I<MAXN;I++)                       set[I]=-I;         }         else         {              flag=1; //有边              FSa=FindSet(pointa);              if(FSa==-pointa)                   set[pointa]=pointa;              FSb=FindSet(pointb);              if(FSb==-pointb)                   set[pointb]=pointb;              if(FSa==FSb)              {                   num=0;                   judge=1;              }                 if(judge==0)              {                      if(FSb==pointb) //pontb是已出现过的根节点                   {                       if(FSa!=-pointa) //当pointa不是还没有出现过的点                       {                            num--;                       }                       set[pointb]=FindSet(pointa);                   }                   else                   {                       if(FSb==-pointb) //pointb还没有出现过                       {                            if(FSa==-pointa) //pointa还没有出现过                            {                                 num++;                            }                            set[pointb]=FindSet(pointa);                       }                       else                       {                            num=0;                            judge=1;                       }                   }              }         }     }     return 0;}

  好久的东西,粗略整理一下。