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);
  }
}