POJ3697

/*
    Memory  Time
    7096K    2641MS
*/

#include <iostream>
#include <string>

using namespace std;

#define HASHLEN 1000117
#define DEMNUM  1000001

int hashTable[HASHLEN];
int factor = 10091;

int pcs[10001];

struct Node {
    int a;
    int b;
    int next;
};
Node dam_node[DEMNUM];

int myq[DEMNUM];

inline int is_demaged(int a, int b) {

    int idx = hashTable[(a * factor + b) % HASHLEN];
    while (idx > 0) {
        if (dam_node[idx].a == a && dam_node[idx].b == b) {
            return 1;
        }
        idx = dam_node[idx].next;
    }
    return 0;
}

int main() {
    int case_i = 0;
    int pc_num = 0, dam_num = 0, i, j, num, pca, pcb, head, tail, hVal, idx, flag;
    while(scanf("%d %d", &pc_num, &dam_num) && !(pc_num == 0 && dam_num == 0)) {

        memset(hashTable, 0x00, sizeof(hashTable));
        memset(pcs, 0x00, sizeof(pcs));
        for (i = 1; i <= dam_num; i++) {
            //input data
            scanf("%d %d", &pca, &pcb);
            if (pca < pcb) {
                dam_node[i].a = pca;
                dam_node[i].b = pcb;
                hVal = (pca * factor + pcb) % HASHLEN;
            } else {
                dam_node[i].a = pcb;
                dam_node[i].b = pca;
                hVal = (pcb * factor + pca) % HASHLEN;
            }
            dam_node[i].next = 0;

            //create hash table
            idx = hashTable[hVal];
            if (idx > 0) {
                dam_node[i].next = idx;
                hashTable[hVal] = i;
            } else {
                hashTable[hVal] = i;
            }
        }
 
        num = 0;
        head = 0;
        tail = 0;
        for (i = 2; i <= pc_num; i++) {
            if (!is_demaged(1,i)) {
                myq[(tail++) % DEMNUM] = i;
                num++;
                pcs[i]=1;
            }
        }
        while(head!=tail) {
            int v = myq[(head++) % DEMNUM];
            for (j = 2; j <= pc_num; j++) {
                if (pcs[j]==1 || v == j) continue;
                if (v < j) {
                    flag = is_demaged(v,j);
                } else {
                    flag = is_demaged(j,v);
                }
                if (!flag) {
                    pcs[j]=1;
                    myq[(tail++) % DEMNUM] = j;
                    num++;
                }
            }
        }
        printf("Case %d: %d
", ++case_i, num);
    }
}