学步园

题目链接:   hdu 2463

题目大意:   给出N(N<=10000)个点的无向完全图

                  现在删掉M条边，问能从1顶点遍历到的顶点有多少个？

解题思路:  1W个点的完全图有n*(n-1)/2条边，不能直接建图，空间复杂度太高

                  只需要记录那些边是已经删除掉了的，删除掉的边用Hash(a+b*10000)记录(或map)

                  把没访问过的点用链表串起来，不能直接用visit[ ]记录，因为每次遍历很耗时

                  也可以用STL库中的set容器存储起来，但STL效率较低

                  BFS每走到某个点时，判断它和没访问过的点中哪些有边，有则走到另一个点

                  PS: Hash的效率比map高，但map可以保证不冲突

代码(Hash+链表):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10003
#define MAX2 2800000
int visit[MAX],list[MAX*2],sum,Top;
int Hash[MAX2+1];

struct snode{
    int w,next;
}Tree[MAX];

int BKDRHash(int k)   //Hash判断边是否是不能走的
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while(k)
    {
        hash = (hash * seed + (k%10))%MAX2;
        k/=10;
    }
    return (hash % MAX2);
}

void BFS(int Star)  //从第一点开始BFS
{
    int i,j,e,s,tempv,tempvv,a,b;
    e=s=0;
    list[s++]=Star;
    visit[Star]=1;
    while(e!=s)
    {
        tempv=list[e++];
        for(i=Top,j=Top;i!=-1;i=Tree[i].next)
        {
            tempvv=Tree[i].w;
            a=(tempv<tempvv)?tempv:tempvv;
			b=(tempv<tempvv)?tempvv:tempv;
            if(Hash[BKDRHash(a+b*10000)]!=1&&!visit[tempvv])  //若该边能走且该点为被访问
            {
                visit[tempvv]=1;
                sum++;
                if(i==Top)              //是链表头则去掉
                {
                    Top=Tree[i].next;
                }
                else                    //不是表头则跳过
                {
                    Tree[j].next=Tree[i].next;
                }
                list[s++]=tempvv;
            }
            else if(i!=Top)
            {
                j=Tree[j].next;
            }
        }
    }
    return ;
}

int main()
{
    int n,m,t=0,i,a,b,temp;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)
            break;
        sum=0;
        memset(Hash,0,sizeof(Hash));
        memset(visit,0,sizeof(visit));
        memset(Tree,-1,sizeof(Tree));
        Top=1;
        Tree[1].w=1;
        for(i=2;i<=n;i++)      //创建链表
        {
            Tree[i-1].next=i;
            Tree[i].w=i;
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            if(b<a)
            {
                temp=a;
                a=b;
                b=temp;
            }
            Hash[BKDRHash(a+b*10000)]=1;  //记录哪些边不能走的
        }
        BFS(1);
        printf("Case %d: %d\n",++t,sum);
    }
    return 0;
}

代码(Map+set):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#define MAX 10010
using namespace std;
set<int> Q;           //**
set<int>:: iterator qi;  //**
map<int,int> S[MAX];
int visit[MAX],list[MAX*2],sum;

void BFS(int Star)
{
    int e,s,tempv,tempvv;
    e=s=0;
    list[s++]=Star;
    visit[Star]=1;
    Q.erase(Star);
    while(e!=s)
    {
        tempv=list[e++];
        for(qi=Q.begin();qi!=Q.end();)   //**
        {
            tempvv=*qi;                  //**
            if(S[tempv][tempvv]!=1&&!visit[tempvv])  //若该点可以访问，则从容器中去掉该点，并且加入队列
            {
                qi=Q.erase(qi);          //**
                sum++;
                visit[tempvv]=1;
                list[s++]=tempvv;
            }
            else                         //**
                qi++;
        }
    }
    return ;
}

int main()
{
    int n,m,t=0,i,a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)
            break;
        sum=0;
        while(!Q.empty())
        {
            Q.clear();
        }
        for(i=1;i<=10002;i++)
        {
            S[i].clear();
        }
        memset(visit,0,sizeof(visit));
        for(i=2;i<=n;i++)
        {
            Q.insert(i);          //往set里面加入元素
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            S[a][b]=S[b][a]=1;    //Map记录哪些边不能走
        }
        BFS(1);
        printf("Case %d: %d\n",++t,sum);
    }
    return 0;
}