poj-1308

//392K  0MS G++ 
#include <cstdio>
#include <cstring>

using namespace std;

const int MAX = 10000;

int UF_set[MAX];

void UF_get_setId(int curId) {
    int parentId = UF_set[curId];
    if (parentId == 0) {
        return;
    }
    while(UF_set[parentId] != parentId) {
        parentId = UF_set[parentId];
    }
    UF_set[curId] = parentId;
    // printf("UF_get_setId %d -> %d\n", curId, parentId);
}

int caseNum = 1;
int edgeNum;

char UF_fill(int begin, int end) {
    UF_get_setId(begin);
    UF_get_setId(end);
    int beginSetId = UF_set[begin];
    int endSetId = UF_set[end];

    // printf("%d -> %d, %d -> %d\n", begin, beginSetId, end, endSetId);

    // both node not be filled before
    if (!beginSetId && !endSetId) {
        UF_set[begin] = begin;
        UF_set[end] = begin;
    } else if (!beginSetId && endSetId) {
        UF_set[beginSetId] = endSetId;
        UF_set[begin] = endSetId;
    } else if (beginSetId && !endSetId) {
        UF_set[endSetId] = beginSetId;
        UF_set[end] = beginSetId;
    } else {
        if (beginSetId == endSetId) {
            // printf("AAA %d %d %d\n", begin, end, beginSetId);
            return 0;
        } else {
            UF_set[beginSetId] = endSetId;
            UF_set[begin] = endSetId;
        }
    }
    return 1;
}
#define INF 9999999

int minNum = INF;
int maxNum;

char inSameSet() {
    // printf("checkInSameSet %d %d\n", minNum, maxNum);
    int curSetId = 0;
    for (int i = minNum; i <= maxNum; i++) {
        UF_get_setId(i);
        if (!curSetId) {
            curSetId = UF_set[i];
        } else {
            if (UF_set[i] && curSetId != UF_set[i]) {
                // printf("%d %d %d\n", i, curSetId, UF_set[i]);
                return 0;
            }
        }
    }
    return 1;
}

int main() {
    int res = 1;
    memset(UF_set, 0, sizeof(UF_set));
    while(1) {
        int begin, end;
        scanf("%d %d", &begin, &end);
        if (begin == -1 && end == -1) {
            return 0;
        } else if (!begin && !end) {

            if (res && inSameSet()) {
                printf("Case %d is a tree.\n", caseNum);
            } else {
                printf("Case %d is not a tree.\n", caseNum);
            }
            caseNum++;
            res = 1;
            maxNum = 0;
            minNum = INF;
            memset(UF_set, 0, sizeof(UF_set));
        } else {
            maxNum = maxNum > begin ? maxNum : begin;
            maxNum = maxNum > end ? maxNum : end;
            minNum = minNum < begin ? minNum: begin;
            minNum = minNum < end ? minNum: end;
            if (begin == end) {
                res = 0;
            }
            if (res) {
                res = UF_fill(begin, end);
            }
        }
    }
}

上面的code其实有问题的，只不过测试数据弱才AC， 除了考虑并查集来检测回路以外，还有些其他的检测: