1，效率不高，优化输入后，还是挺废时间的，第一个版本，代码贴上：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct{ //存储不合适的边
	int v, u;
}ary;
ary num[1000007];

typedef struct{//队列
	int n, before;
}queue;
queue que[10007];

bool search[10007];
int input()
{
    int r=0;
    char ch;
    while((ch=getchar())>='0'&&ch<='9')
    	r=r*10+ch-'0';
    return r;
}
int n ,m;
bool towsearch(int v, int u){//二分查找
	int left = 0, mid, right = m-1;
	if(v > u){
		int temp = v; v = u; u = temp;
	}
	while(left <= right){
		mid = (left + right) / 2;
		if(num[mid].v == v && num[mid].u == u){
			return true;
		}
		else if((num[mid].v == v && num[mid].u < u) || (num[mid].v < v)){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}
	}
	return false;
}


int cmp (const void*a, const void*b){//快速排序
	ary* aa = (ary*)a;
	ary* bb = (ary*)b;
	if(aa->v > bb->v){
		return 1;
	}
	else if(aa->v < bb->v){
		return -1;
	}
	else{
		if(aa->u > bb->u)
			return 1;
		else if(aa->u == bb->u)
			return 0;
		else 
			return -1;
	}
}

int main(){
	int temp = 0;
	while(n = input(), m = input(),n , m){
		temp++;
		memset(search, false, sizeof(search));
		int a,b;
		for(int i = 0; i < m; ++i){
            a = input();
            b = input();
			//scanf("%d%d", &a, &b);
			if(a > b){
				int t = a;
				a = b;
				b = t;
			}
			num[i].v = a;
			num[i].u = b;
		}

		qsort(num, m, sizeof(num[0]), cmp);

		int front, rear;

		front = 0;//BFS
		rear = 0;
		int sum = 0;
		que[front].n = 1;
		que[front].before = 0;
		search[1]=true;
		while(front <= rear ){
			for(int i = 2; i <= n; ++i){
				if(!search[i] && !towsearch(que[front].n,i)){//若点没被visit && 若此边合适即入队，点i即可与1相通
					rear++;
					que[rear].n = i;
					que[rear].before = que[front].n;
					search[i] = true;
					sum++;
					if(m-1  == sum)
						break;

				}
			}
			++front;
		}
		printf("Case %d: %d\n", temp, sum);
	}
	return 0;
}



第二种，除了优化了输入，还把搜索区间优化了：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define mod 1000117
#define smod 10091
typedef struct{ //存储不合适的边
	int x, y;
}ary;
ary num[mod];
int next[mod], hash[mod], point[smod], que[smod];
int endList;

int input()
{
    int r=0;
    char ch;
    while((ch=getchar())>='0'&&ch<='9')
    	r=r*10+ch-'0';
    return r;
}

void insert(int a, int b){
    int code = (a * smod + b) % mod;
    num[endList].x = a;
    num[endList].y = b;
    next[endList] = hash[code];
    hash[code] = endList++;
}
bool find(int a, int b){
	if(a > b){
		int t = a;
		a = b;
		b = t;
	}
	int code = (a * smod + b) % mod;
    for (int i = hash[code]; i > -1;i = next[i])
        if(num[i].x == a && num[i].y == b)
			return true;
    return false;
}
int main(){
    int n, m, temp = 0;
    while(n = input(), m = input(),n , m){
		++temp ;
        int x, y;
		endList = 0;
		memset(hash,-1,sizeof hash);
        for(int i = 0; i < m; ++i){
			x = input();
			y = input();
			//scanf("%d%d", &x, &y);
			if(x > y){
				insert(y, x);
			}
			else{
				insert(x, y);
			}
		}
		int front = 0;
        int rear = 0;
		que[front] = 1;
		for(int i = 2; i <= n; ++i){
			point[i]=i;
		}
		int sum = 0;
		while(front <= rear){
			for(int i = 2; i <= n; ){
				if(!find(que[front], point[i])){
					rear++;
					que[rear] = point[i];
					point[i] = point[n];
					n--;
					sum++;
				}
				else{
					i++;
				}
			}
			front++;
		}
		printf("Case %d: %d\n", temp, sum);
	}
	return 0;
}


第三种，关键是数组模拟，链表。不贴了