1325.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include <iostream>
#include <cstdio>
using namespace std;
int set[100010];
int degree[100010];
bool hash[100010];
void makeset()
{
    int i;
    for (i = 1; i <= 100000; i++)
    {
        set[i] = i;
        hash[i] = false;
		degree[i] = 0;
    }
}
int find(int x)
{
    int i, r = x;
    while (r != set[r])
    {
        r = set[r];
    }
    while (x != r)
    {
        i = set[x];
        set[x] = r;
        x = i;
    }
    return r;
}
void unions(int x, int y)
{
    int a = find(x);
    int b = find(y);
    if (a != b)
    {
        set[a] = b;
    }
}
int main()
{
    int a, b, i, node = 0, edge = 0, gen = 0, onde = 0, made = 0, test = 0;
    makeset();
    while (scanf("%d %d", &a, &b) == 2) 
    {
        if (a == 0 && b == 0)
        {
            for (i = 1; i <= 100000; i++)
            {
				onde += degree[i] == 1;
				made += degree[i] > 1;
                if (hash[i] == true && set[i] == i)
                {
                    gen++;
                }
            }
            if ((gen == 1 && edge == node - 1 && onde == node - 1 && made == 0) || node == 0)
            {
                cout << "Case " << ++test << " is a tree." << endl;
            }
            else
            {
                cout << "Case " << ++test << " is not a tree." << endl;
            }
            gen  = 0;
            edge = 0;
            node = 0;
			onde = 0;
			made = 0;
            makeset();
        }
        else if (a < 0 && b < 0)
        {
            break;
        }
        else
        {
			degree[b] ++;
            node += hash[a] == false;
            node += hash[b] == false;
            hash[a] = true;
            hash[b] = true;
            edge++;
            unions(a, b);
        }
    }
    return 0;
}