sdut Thrall’s Dream(判断任意两点是否联通)

题意：给一张无向图，判断任意两点是否联通；

思路：bfs枚举个点，逐个遍历；

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int con[2005][2005];
vector<short> v[2005];
int n,m;
int judge()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            if(!con[i][j]&&!con[j][i]) return 0;
        }
    }
    return 1;
}
void bfs(int x)
{
    queue<short> que;
    que.push(x);
    while(!que.empty())
    {
        short temp=que.front();
        que.pop();
        if(temp<x)
        {
            for(int i=1;i<=n;i++)
            {
                if(con[temp][i])
                {
                    con[x][i]=1;
                }
            }
        }
        else
        {
            for(int i=0;i<v[temp].size();i++)
            {
                if(!con[x][v[temp][i]])
                {
                    con[x][v[temp][i]]=1;
                    que.push(v[temp][i]);//相邻点入队列
                }
            }
        }
    }
}
int main()
{
    int i,j,k,t,a,b;
    while(scanf("%d",&t)!=EOF)
    {
        for(i=1;i<=t;i++)
        {
            memset(con,0,sizeof(con));
            memset(v,0,sizeof(v));
            scanf("%d%d",&n,&m);
            for(j=0;j<m;j++)
            {
                scanf("%d%d",&a,&b);
                v[a].push_back(b);
            }
            for(k=1;k<=n;k++)
            {
                bfs(k);
            }
            printf("Case %d: ",i);
            if(judge()) printf("Kalimdor is just ahead
");
            else printf("The Burning Shadow consume us all
");
        }
    }
    return 0;
}