poj 1308 Is It A Tree?

Memory:156K Time:0MS

题意：

    给出一系列节点对，判断是不是树。是树的条件是：只有一个根节点，没有指向根节点的边，除了根节点每个节点都只有一条边指向它，只有一条唯一的路从根节点到其他各个节点。空树是一棵树。森林不是树。

 

思路：

   这么多条件总结起来其实只要判断：①.树的节点数v是不是等于边的条数u+1，②判断有没有环，③考虑空树的情况就可以了。主要是数顶点，我是把所有节点存在数组num里，再排个序，在找出不同的个数，再跟边比较。第二种用到了并查集，一条边一条边加进去，看是否有祖先节点相同的情况，有的话就是存在环。第三种最简单，输入只有两个0的话，直接判断是棵树。

 

 

源程序1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 100

typedef struct
{
    int x, y;
}node;
node nodes[N];
int t, parent[N], rank[N], num[N], count;

int find(int x)
{
    int y, z;

    y = x;
    while(parent[y]!= y)
        y = parent[y];
    while(x != y)
    {
        z = parent[x];
        parent[x] = y;
        x = z;
    }
    return y;
}
void _union(int x, int y)
{
    if(rank[x] > rank[y])
        parent[y] = x;
    else {
        if(rank[x] == rank[y])
            rank[y]++;
        parent[x] = y;
    }
}
void fun(int n)
{
    int i, x, y;
    int ok = 0;
    if(count != n+1)
        ok = 1;
    else
    {
        for(i=0; i<n; i++)
        {
            x = find(nodes[i].x);
            y = find(nodes[i].y);
            if(x == y)
            {
                ok = 1;
                break;
            }
            else
                _union(nodes[i].x, nodes[i].y);
        }
    }
    t++;
    if(ok)
        printf("Case %d is not a tree.\n", t);
    else printf("Case %d is a tree.\n", t);
}

int cmp(const void *p, const void *q)
{
    return *(int *)p > *(int *)q ? 1 : -1;
}

int main()
{
    int i, j, k, s;
    int a, b, c;
    k = 0;
    s = 0;
    while(scanf("%d%d", &a, &b))
    {
        if(a == -1 && b == -1)
            break;
        if(!a && !b)
        {
            if(!k)
            {
                t++;
                printf("Case %d is a tree.\n", t);
                continue;
            }
            qsort(num, s, sizeof(num[0]), cmp);
            count = 1;
            c = num[0];
            for(i=1; i<s; i++)
            {
                if(num[i] != c)
                {
                    count ++;
                    c = num[i];
                }
            }
            fun(k);
            k = 0;
            s = 0;
            memset(num, 0, sizeof(num));
            memset(nodes, 0, sizeof(nodes));
            memset(rank, 0, sizeof(rank));
            continue;
        }
        nodes[k].x = a;
        nodes[k].y = b;
        parent[a] = a;
        parent[b] = b;
        num[s++] = a;
        num[s++] = b;
        k++;
    }
    return 0;
}
源程序2
这是以前做的，没有用到并查集，更简单。

Memory: 132K

Time: 0MS

#include <stdio.h>
#include <string.h>
#define N 20

int isexit(int a, int nodes[], int n)
{
    int i;
    for(i=0; i<n; i++)
    {
        if(a == nodes[i])
            return 1;
    }
    return 0;
}

int main()
{

    int node1[N], node2[N];
    int nodes[N*2];
    int i=0, m=0, j, k, flag = 0, falg = 1, count;
    
    scanf("%d%d", &node1[0], &node2[0]);
    while(node1[0]!=-1 && node2[0] != -1)
    {
        
        flag = 0;
        m++;
    
        while(node1[i]!=0 && node2[i] != 0)
        {
            i++;
            scanf("%d%d", &node1[i], &node2[i]);
        }
        count = 0;
        for(j=0; j<i; j++)
        {
            if(!isexit(node1[j], nodes, count))
                nodes[count++] = node1[j];
            if(!isexit(node2[j], nodes, count))
                nodes[count++] = node2[j];
        }
        if(count != i+1)
            flag = 1;

        if(node1[0] == 0 && node2[0] == 0)
            flag = 0;
        if(flag)
            printf("Case %d is not a tree.\n", m);
        else
            printf("Case %d is a tree.\n", m);
        i = 0;
        memset(node1, 0, sizeof(node1));
        memset(node2, 0, sizeof(node2));
        scanf("%d%d", &node1[i], &node2[i]);
    }
}