HDOJ - Is It A Tree?

This question mainly investigates “ Union checking set ” This knowledge .

Existing problems

1. because HDOJ The test data of this question is weak , Online Some answers No need to search the set , Just checking the penetration can AC
2. Some answers Put and search the relevant codes , But it doesn't work at all （if Judge the condition ）

1、2 Our algorithm can easily find counterexamples （ A ring + A tree ）, Because they do not judge connectivity or do not judge enough

3. The single point case is generally not considered （ Only a single point or a graph + One point ）

Pit of test data

HDOJ Incomplete input of test data on , There are test cases 0 0 It is truncated without input

The verification code is as follows ：

#include <bits/stdc++.h>
using namespace std;

int rudu[100005];
int count1 = 1;
void z()
{
    
    int f = 0;
    for (int i = 1; i <= 100004; i++)
    {
    
        if (rudu[i] == 0)
            f++;
        if (rudu[i] > 1)
            f = 2;
    }

    if (f == 1)
        printf("Case %d is a tree.\n", count1);
    else
        printf("Case %d is not a tree.\n", count1);
    count1++;
}
int main()
{
    
    int aa, b;
    while (cin >> aa >> b)
    {
    
        if (aa == -1 && b == -1)
            break;
        if (aa == 0 && b == 0)
        {
    
            printf("Case %d is a tree.\n", count1);
            count1++;
            continue;
        }
        fill(rudu, rudu + 100005, -1);
        rudu[aa] = 0;
        rudu[b] = 0;
        if (aa != b)
            rudu[b]++;
        while (cin >> aa >> b)
        {
    
            if (rudu[aa] == -1)
                rudu[aa] = 0;
            if (rudu[b] == -1)
                rudu[b] = 0;
            if (aa != b)
                rudu[b]++;

            if (aa == 0 && b == 0)
            {
    
                z();
                break;
            }
        }
    }
}

If the 41 That's ok while Change it to ：

while (1)
{
    
    cin >> aa >> b;

Can not AC, If it's changed to ：

while (1)
{
    
    if (!(cin >> aa >> b))
        break;

Then you can AC

Correct code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10010;
int node[maxn]; //  node ( The default is 0,  Indicates that the point does not exist )
int in[maxn];   //  The degree of ( The default is -1,  Indicates that the point does not exist )

int find(int x)
{
    
    //  Enable this point ,  Initialize to itself 
    if (node[x] == 0)
    {
    
        node[x] = x;
        return x;
    }

    while (node[x] != x)
        x = node[x];
    return x;
}

void merge(int a, int b)
{
    
    a = find(a);
    b = find(b);
    node[a] = b;
}

int main()
{
    
    int a, b;
    int count = 1;
    while (cin >> a >> b)
    {
    
        if (a == -1 && b == -1)
            break;
        if (a == 0 && b == 0)
        {
    
            printf("Case %d is a tree.\n", count);
            count++;
            continue;
        }

        memset(node, 0, sizeof(node));
        fill(in, in + maxn, -1);

        merge(a, b);
        in[a] = 0;
        in[b] = 0;
        if (a != b)
            in[b]++;

        while (cin >> a >> b)
        {
    
            merge(a, b);
            if (in[a] == -1)
                in[a] = 0;
            if (in[b] == -1)
                in[b] = 0;
            if (a != b)
                in[b]++;

            if (a == 0 && b == 0)
            {
    
                int sum = 0;
                int flag = -1;
                for (int i = 1; i < maxn; i++)
                {
    
                    if (node[i] == i)
                        sum++;
                    if (in[i] == 0)
                        flag++;
                    if (in[i] > 1)
                        flag = 1;
                }

                if (sum == 1 && flag == 0)
                    printf("Case %d is a tree.\n", count);
                else
                    printf("Case %d is not a tree.\n", count);
                count++;
                break;
            }
        }
    }
}