PKU 3697 USTC campus network
http://poj.org/problem?id=3697
ノード数nの完全グラフからm個の辺を取ったものを考える。
このグラフのノード0からたどれるノードの個数を数えろというような問題。
ハッシュと入力の高速化で頑張りました。
typedef struct _node{ PI val; _node*next; }node; const int hashMod=3000000; node* hash[hashMod]; node ent[1000000]; int sz; bool app(int a,int b){ int ha=(a*193707721LL+b)%hashMod; for(node*p=hash[ha];p;p=p->next) if(p->val.F==a && p->val.S==b)return true; return false; } void insert(int a,int b){ if(a>b)swap(a,b); int ha=(a*193707721LL+b)%hashMod; for(node*p=hash[ha];p;p=p->next) if(p->val.F==a && p->val.S==b)return; node*p=hash[ha]; hash[ha]=ent+sz++; hash[ha]->val=mp(a,b); hash[ha]->next=p; } char input[30000000]; char*pos; int getnum(){ int ret,c; while(!isdigit(c=*pos++)); ret=c&15; while(isdigit(c=*pos++))ret=(ret<<3)+(ret<<1)+(c&15); return ret; } bool vis[10000]; int n; int ans; void dfs(int v){ vis[v]=true; ++ans; rep(i,n){ if(vis[i])continue; if(app(min(i,v),max(i,v)))continue; dfs(i); } } main(){ fread(input,sizeof(input),1,stdin); pos=input; char c; if(cin>>c)for(;;); int m; int ca=0; while(true){ n=getnum(); m=getnum(); if(n==0 && m==0)break; memset(hash,0,sizeof(hash)); sz=0; rep(i,m) insert(getnum()-1,getnum()-1); ans=-1; memset(vis,0,sizeof(vis)); dfs(0); printf("Case %d: %d\n",++ca,ans); } }