L - Points on Cycle

        这个题本来是应该要用并查集来解决的,但是仔细想想也可以不用,根据离散数学,树是没有连通回路的图,而且  节点数=边数+1,所以,通过判断这棵树有没有同时指向一个点的多条边,以及 节点数=边数+1就行了,然后空树也是树,所以这样就截出来了。


NOTE
when output, if the absolute difference between the coordinate values X1 and X2 is smaller than 0.0005, we assume they are equal.
 

Sample Input

2
1.500 2.000
563.585 1.251
 

Sample Output

0.982 -2.299 -2.482 0.299
-280.709 -488.704 -282.876 487.453


下面是我的代码:


#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=10000+10;
int nodeL[maxn], nodeR[maxn];
int nleft, nright, nmax;
int edge, node;
int icase=0;
bool isTree;
void Init()
{
    memset(nodeL, 0, sizeof(nodeL));
    memset(nodeR, 0, sizeof(nodeR));
    edge=0;
    node=0;
    nmax=maxn-1;
}
bool CountNode()
{
    for(int i=0;i<=nmax;i++)
    {
        if(nodeR[i]>1)return false;
        if(nodeL[i] || nodeR[i])node++;
    }
    return true;
}
int main()
{
    Init();
    while(cin>>nleft>>nright && nleft!=-1 && nright!=-1)    //判断输入是否结束
    {
        if(nleft || nright)   //如果输入的值不是0则放入数组统计
        {
            nodeL[nleft]++;
            nodeR[nright]++;
            edge++;
            nmax=nmax>nleft?nmax:nleft;
            nmax=nmax>nright?nmax:nright;
        }
        else               //输入的值为0则进行运算并在之后清空操作
        {
            if(CountNode() && node==edge+1)isTree=true;
            else isTree=false;
            if(!edge)isTree=true;
            if(isTree)cout<<"Case "<<++icase<<" is a tree."<<endl;
            else cout<<"Case "<<++icase<<" is not a tree."<<endl;
            Init();
        }
    }
    return 0;
};