/*
大体解释：使用floyd计算每个节点与其他节点的最短距离，最短距离有大于7的说明六度分离理论不成立。
*/
#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int LEN=205;
const int INF=0x3f3f3f3f;
int vis[LEN], know[LEN][LEN], dis[LEN];
void init()
{
int i, j;
for(i=0; i<=LEN; ++i)
for(j=0; j<=LEN; ++j)
i==j ? know[i][j]=0 : know[i][j]=INF;
}
void floyd(const int &n)
{
int i, j, k;
for(k=0; k<n; k++)
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(know[i][j]>know[i][k]+know[k][j])
know[i][j]=know[i][k]+know[k][j];
}
int judge(const int &n)
{
int i, j, mark=1;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(know[i][j]>7)
{
mark=0; break;
}
return mark;
}
int main()
{
int i, j, n, m, a, b;
while(cin>>n>>m)
{
//init();
//这里使用了一下0x3f的技巧
memset(know, 0x3f, sizeof(know));
for(i=0; i<m; i++)
cin>>a>>b, know[a][b]=know[b][a]=1;
floyd(n);
if(judge(n))
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;
}
| 
转播
