PTA 資料結構與算法題目集（中文）7-7 六度空間 (30分) 題解

我的GIS/CS學習筆記：​​https://github.com/yunwei37/ZJU-CS-GIS-ClassNotes​​ <一個浙江大學大學生的計算機、地理資訊科學知識庫 >

還有不少資料結構和算法相關的筆記以及pta題解哦x

“六度空間”理論又稱作“六度分隔（Six Degrees of Separation）”理論。這個理論可以通俗地闡述為：“你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過五個人你就能夠認識任何一個陌生人。”

“六度空間”理論雖然得到廣泛的認同，并且正在得到越來越多的應用。但是數十年來，試圖驗證這個理論始終是許多社會學家努力追求的目标。然而由于曆史的原因，這樣的研究具有太大的局限性和困難。随着當代人的聯絡主要依賴于電話、短信、微信以及網際網路上即時通信等工具，能夠展現社交網絡關系的一手資料已經逐漸使得“六度空間”理論的驗證成為可能。

假如給你一個社交網絡圖，請你對每個節點計算符合“六度空間”理論的結點占結點總數的百分比。

輸入格式:

輸入第1行給出兩個正整數，分别表示社交網絡圖的結點數N（1<N≤10​3​​，表示人數）、邊數M（≤33×N，表示社交關系數）。随後的M行對應M條邊，每行給出一對正整數，分别是該條邊直接連通的兩個結點的編号（節點從1到N編号）。

輸出格式:

對每個結點輸出與該結點距離不超過6的結點數占結點總數的百分比，精确到小數點後2位。每個結節點輸出一行，格式為“結點編号:（空格）百分比%”。

輸入樣例:

10 9

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

輸出樣例:

1: 70.00%

2: 80.00%

3: 90.00%

4: 100.00%

5: 100.00%

6: 100.00%

7: 100.00%

8: 90.00%

9: 80.00%

10: 70.00%

思路

當時的思路是使用單源無權最短路算法，疊代計算路徑長度，

當出現第一個節點路徑為7時退出循環，計算經過的節點個數

（現在看起來好蠢…BFS好像挺香的）

#include<stdio.h>
//使用單源無權最短路算法，疊代計算路徑長度，
//當出現第一個節點路徑為7時退出循環，計算經過的節點個數 
int a[10001][10001] = { 0 };// 
int v[10001] = { 0 };
//visit表和鄰接矩陣 
struct queue {
int a[10001];
int first, last;
int sum;
}q;

void push(int x) {
if (q.first == 999)
q.first = 0;
else q.first++;
q.a[q.first] = x;
q.sum++;
}

int pop() {
int t = q.a[q.last];
if (q.last == 999)
q.last = 0;
else q.last++;
q.sum--;
return t;
}
//循環隊列 
int main() {
int n, m;
int i, j;
scanf("%d %d", &n, &m);
int v1, v2;
for (i = 0; i < m; ++i) {
scanf("%d%d", &v1, &v2);
a[v1][v2] = 1;
a[v2][v1] = 1;
  }
int len, now, num;//目前邊數值，作為通路标記； 

for (i = 1; i <= n; ++i){
//隊列初始化 
q.sum = 0;
q.first = 999;
q.last =0;
len = 0;
num = 1;
push(i);
for (j = 1; j <= n; ++j)
v[j] = -1;
v[i]=0;
while (1) {
if (q.sum==0) {
break;
      }
now = pop();
for (j = 1; j <= n; ++j) {
if (a[now][j] && v[j] == -1) {
push(j);
v[j] = v[now]+1;
if(v[j]==7) break;
++num;
        }
      }
if(v[j]==7) break;
    }
double per = 1.0*num / n * 100;
printf("%d: %.2f%%\n", i, per);
  }
return 0;
}