看心情填坑

http://poj.org/problem?id=3697

感觉有点有趣所以来写一下。

题意简单粗暴，给你一个完全图然后去掉若干条边问和点1联通的点数。

直接上邻接矩阵bfsO（n²）显然不用玩，然后考虑效率更好的标(youhua)算(baoli)。

我们可以把去掉的边hash挂链然后每次需要查找的时候就去hash链上寻找，找不到的话说明这条边存在。

然后考虑bfs的优化，因为是一个完全图，所以我们可以把所有的点挂在一个链表上，每次搜到就删除，可以快很多，大概最坏情况虽然也是O(n²)但是常数很小就可以过

#include<cstdio>
#include<cstring>
using namespace std;
int n,m,x,y,cnt,test;
struct hash{
	int x,y,next;
}h[2000005];
int head[1000007],dl[10007],next[10005],pre[10005],Head,Tail;
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
void insert(int x,int y){
	int key=(1LL*x*x%1000007+1LL*y*y%1000007)%1000007;
	cnt++;
	h[cnt].next=head[key];
	h[cnt].x=x;
	h[cnt].y=y;
	head[key]=cnt;
}
inline bool find(int x,int y){
	int key=(1LL*x*x%1000007+1LL*y*y%1000007)%1000007;
	for(int i=head[key];i;i=h[i].next){
		if((h[i].x==x)&&(h[i].y==y))return false;
		if((h[i].x==y)&&(h[i].y==x))return false;
	}
	return true;
}
inline int bfs(){
	int l=1,r=1;
	dl[1]=1;
	while(r>=l){
		for(int i=Head;i;i=next[i]){
			if(find(dl[l],i)){
				r++;
				dl[r]=i;
				if(i==Head)Head=next[i];
				else next[pre[i]]=next[i];
				if(i==Tail)Tail=pre[i];
				else pre[next[i]]=pre[i];
			}
		}
		l++;
	}
	return r-1;
}
int main(){
	while(n=read(),m=read(),n+m){
		memset(head,0,sizeof(head));
		cnt=0;
		for(int i=1;i<=m;i++){
			x=read();
			y=read();
			insert(x,y);
		}
		for(int i=2;i<n;i++)next[i]=i+1,pre[i+1]=i;
		Head=2;Tail=n;
		printf("Case %d: %d\n",++test,bfs());
	}
}