UVa 615

From Algorithmist
Jump to navigation Jump to search
#include <stdio.h>

struct NodeNum {
    int num;
    NodeNum *next;
};
NodeNum *node_num_list = 0;


struct Edge {
    int from, to;
    Edge *next;
    Edge(int f, int t);
};
Edge *edge_list;



void ClearNodeNumList() {
    NodeNum *p = node_num_list, *q;
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    node_num_list = new NodeNum;
    node_num_list->next = 0;
    node_num_list->num = -42;
}


int GetNodeNum(int n) {
    NodeNum *p = node_num_list;
    int c = 0;
    while (p->next) {
        p = p->next;
        if (p->num == n) return c;
        c++;
    }
    p->next = new NodeNum;
    p = p->next;
    p->num = n;
    p->next = 0;
    return c;
}


int NumNodes() {
    NodeNum *p = node_num_list->next;
    int c = 0;
    while (p) {
        c++; p = p->next;
    }
    return c;
}


Edge::Edge(int f, int t) {
    from = GetNodeNum(f);
    to = GetNodeNum(t);
}


int NumEdgesTo(Edge *p, int node_no) {
    int c = 0;
    while (p) {
        if (p->to == node_no) c++;
        p = p->next;
    }
    return c;
}


void Visit(Edge *edge_list, int node, int visited[]) {
    Edge *p = edge_list;
    visited[node]++;
    while (p) {
        if (p->from == node) {
            Visit(edge_list, p->to, visited);
        }
        p = p->next;
    }
}



int IsATree(Edge *edge_list) {
    int n_nodes = NumNodes();
    int i, root_node = -1;
    int n_edges_to;


    if (n_nodes == 0) return 1;

    for (i=0; i<n_nodes; i++) {
        n_edges_to = NumEdgesTo(edge_list, i);
        if (n_edges_to == 0) {
            if (root_node == -1) {
                root_node = i;
            } else {
                return 0;
            }
        } else if (n_edges_to != 1) {
            return 0;
        }
    }
    if (root_node == -1) return 0;

    int *visited = new int[n_nodes];
    for (i=0; i<n_nodes; i++) visited[i] = 0;


    Visit(edge_list, root_node, visited);


    for (i=0; i<n_nodes; i++) {
        if (visited[i] != 1) {
            delete[]visited;
            return 0;
        }
    }

    delete[]visited;
    return 1;
}


int main() {
    int case_no = 1;
    int from, to;
    FILE *inf = stdin;

    while (fscanf(inf, "%d %d", &from, &to), from != -1 || to != -1) {

        edge_list = 0;
        ClearNodeNumList();

        while (from || to) {
            Edge *new_edge = new Edge(from, to);
            new_edge->next = edge_list;
            edge_list = new_edge;
            fscanf(inf, "%d %d", &from, &to);
        }

        int is_tree = IsATree(edge_list);
        printf("Case %d is %sa tree.\n", case_no++, is_tree ? "" : "not ");

        while (edge_list) {
            Edge *e = edge_list;
            edge_list = edge_list->next;
            delete e;
        }
    }
    return 0;
}

Solutions[edit]