HDU-1869-六度分離_floyd算法_Quentin

六度分離（floyd算法）

🔗題目連結

🔗floyd算法圖文詳解(全)

題目描述：

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

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

輸入：

    本題目包含多組測試，請處理到檔案結束。

    對于每組測試，第一行包含兩個整數N,M(0<N<100,0<M<200),分别代表HDU裡的人數（這些人分别編成0~N-1号)，以及他們之間的關系。

    接下來有M行，每行兩個整數A,B(0<=A,B<N)表示HDU裡編号為A和編号B的人互相認識。

除了這M組關系，其他任意兩人之間均不相識。

輸出：

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

輸入樣例：

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

題目分析：

    這道題就是看圖是否連通，各頂點之間是否都能夠到達。我們可以利用floyd算法，創造一個二維數組來表示這些點之間的連通性，如果連通就置為1。當然數組的初始化也要按照floyd算法的要求，頂點與頂點本身置為0，其餘置為無窮大，這裡無窮大用#define INF 0x3f3f3f3f來表示

代碼示例：

#include <iostream>
#define MAX 101
#define INF 0x3f3f3f3f
using namespace std;
int main(){
	int N, M, A, B, temp;
	while(scanf("%d %d", &N, &M) != EOF){//一直通路到檔案末尾 
		int num[MAX][MAX];
		temp = 0;
		for(int i=0; i<N; i++){//初始化數組 
			for(int j=0; j<N; j++){
				if(i==j)
					num[i][j] = 0;//頂點本身置為0 
				else
					num[i][j] = INF;//其餘置為無窮大 
			}
		}
		for(int i=0; i<M; i++){//把關系逐個輸入 
			cin >> A >> B;
			num[A][B] = 1;
			num[B][A] = 1;
		}
		for(int k=0; k<N; k++){//floyd的套路開始了 
			for(int i=0; i<N; i++){
				for(int j=0; j<N; j++){
					if(num[i][j] > num[i][k]+num[k][j]){
						num[i][j] = num[i][k] + num[k][j];
					}
				}
			}
		}
		for(int i=0; i<N; i++){//檢測環節 
			for(int j=0; j<N; j++){
				if(num[i][j] > 7){//這個判斷條件要注意 
					temp = 1;
					break;
				}
			}
		}
		if(temp == 1)
			cout << "No" << endl;
		else
			cout << "Yes" << endl;
	}
	return 0;
}
           

《羊卓的楊的算法筆記》：🔗連結

哔哩哔哩/bilibili：羊卓的楊

羊卓的楊公衆号：