六度分离

8 7
0 1
1 2
2 3
3 4
4 5
5 6
6 7
8 8
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0

Yes
Yes

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m;
int g[111][111];

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(g,63,sizeof(g));
        for(int i=0;i<n;i++) g[i][i]=0;
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            g[a][b]=g[b][a]=1;
        }
        for(int k=0;k<n;k++)
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
                }
            }
        }
        bool flag=true;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(g[i][j]>7)
                {
                    flag=false;
                    break;
                }
            }
            if(flag==false) break;
        }
        if(flag) puts("Yes");
        else puts("No");
    }
}

HDOJ 1869 六度分离,布布扣,bubuko.com

HDOJ 1869 六度分离

原文：http://blog.csdn.net/ck_boss/article/details/25338905