Problem Description

1967年，美國著名的社會學家斯坦利·米爾格蘭姆提出了一個名為“小世界現象(small world phenomenon)”的著名假說，大意是說，任何2個素不相識的人中間最多只隔著6個人，即只用6個人就可以將他們聯系在一起，因此他的理論也被稱為“六度分離”理論(six degrees of separation)。雖然米爾格蘭姆的理論屢屢應驗，一直也有很多社會學家對其興趣濃厚，但是在30多年的時間里，它從來就沒有得到過嚴謹的證明，只是一種帶有傳奇色彩的假說而已。?

Lele對這個理論相當有興趣，于是，他在HDU里對N個人展開了調查。他已經得到了他們之間的相識關系，現在就請你幫他驗證一下“六度分離”是否成立吧。

Input

本題目包含多組測試，請處理到文件結束。?
對于每組測試，第一行包含兩個整數N,M(0<N<100,0<M<200),分別代表HDU里的人數（這些人分別編成0~N-1號)，以及他們之間的關系。?
接下來有M行，每行兩個整數A,B(0<=A,B<N)表示HDU里編號為A和編號B的人互相認識。?
除了這M組關系，其他任意兩人之間均不相識。?

Output

對于每組測試，如果數據符合“六度分離”理論就在一行里輸出"Yes"，否則輸出"No"。

Sample Input

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

Sample Output

Yes
Yes

思路：實質是一個 Floyd 求最短路問題，存圖后 Floyd 枚舉所有人的連通性，如果能連通就更新最少認識的人數，最后枚舉所有人，判斷是否有大于 7 的，若大于 7 則輸出 No

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-6 #define MOD 16007 #define INF 0x3f3f3f3f #define N 1001 #define LL long long using namespace std; int n,m; int G[N][N]; int main(){while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){memset(G,INF,sizeof(G));for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i==j)G[i][j]=0;while(m--){int x,y;scanf("%d%d",&x,&y);if(x!=y){G[x][y]=1;G[y][x]=1;}}for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(G[i][k]+G[k][j]<G[i][j])G[i][j]=G[i][k]+G[k][j];bool flag=false;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(G[i][j]>7){flag=true;break;}}if(flag)break;}if(flag)printf("No\n");elseprintf("Yes\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的六度分离（HDU-1869）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。