06-圖3 六度空間(c/c++)

“六度空間”理論又稱作“六度分隔（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%

思路

要特别注意輸出的格式和起始的結點編号，尤其是百分号也是分兩種的…最好直接複制過來。

重點在于深度的判斷，用BFS的方法周遊圖，設定一個變量來儲存每層的最後一個結點，如果目前結點等于此變量，深度+1。

用DFS的方法，每次遞歸周遊一個結點深度+1，退出遞歸回溯一個結點深度-1，逾時過不去最後一個測試點，在處理環上時間複雜度太高了

BFS全部AC

代碼

BFS

#include<bits/stdc++.h>
#define MAX 1001

using namespace std;

bool vis[MAX]={false};
vector<int>Adj[MAX];
double n;//與該結點距離不超過6的結點數

//廣度優先搜尋
void BFS(int i,int depth){
	int last=i,temp;
	vis[i]=true;
	queue<int>q;
	q.push(i);
	while(!q.empty()){
		i=q.front();
		q.pop();
		for(int j=0;j<Adj[i].size();j++){
			if(vis[Adj[i][j]]==false&&depth<6){
				n++;
				temp=Adj[i][j];
				q.push(Adj[i][j]);
				vis[Adj[i][j]]=true;
			}
		
		}
		if(i==last){
			depth++;
			last=temp;//每層的最後一個結點
		}
	} 	
} 

int main() {
	double N,M;
	cin>>N>>M;
	int n1,n2;
	for(int i=0;i<M;i++){
		cin>>n1>>n2;
		Adj[n1].push_back(n2);//Adj[n1][j]=n2; j=0;j++;
		Adj[n2].push_back(n1);
	} 
	for(int i=1;i<N+1;i++){
		int depth=0;
		n=1;
		BFS(i,depth);
		cout<<i<<": "<<fixed<<setprecision(2)<<n/N*100.00<<"%"<<endl; 
		fill(vis,vis+MAX,false);
		//memset(vis,false,sizeof(vis));
	} 
	return 0;
}
           

DFS

#include<bits/stdc++.h>
#define MAX 1001

using namespace std;

bool vis[MAX]={false};
vector<int>Adj[MAX];
double n;//與該結點距離不超過6的結點數

//深度優先搜尋
void DFS(int i,int depth){
	vis[i]=true;
	for(int j=0;j<Adj[i].size();j++){
		//cout<<Adj[i][j]<<" "<<depth<<endl;
		if(vis[Adj[i][j]]==false&&depth<6){
			depth++;
			n++;
			DFS(Adj[i][j],depth);
			depth--;
		}
		else if(vis[Adj[i][j]]==true&&depth<6){
			depth++;
			DFS(Adj[i][j],depth);
			depth--;
		}
		else{
			break;
		}
	}
} 

int main() {
	double N,M;
	cin>>N>>M;
	int n1,n2;
	for(int i=0;i<M;i++){
		cin>>n1>>n2;
		Adj[n1].push_back(n2);//Adj[n1][j]=n2; j=0;j++;
		Adj[n2].push_back(n1);
	} 
	for(int i=1;i<N+1;i++){
		int depth=0;
		n=1;
		DFS(i,depth);
		//cout<<n<<endl;
		cout<<i<<": "<<fixed<<setprecision(2)<<n/N*100.00<<"%"<<endl; 
		memset(vis,false,sizeof(vis));
	} 
	return 0;
}
           

Tip

memset按位元組輸入，隻能指派為0或-1，限制性較強。

a[n]
memset(a,value,sizeof(a));
           

fill可以任意指派，使用簡便

a[n];
fill(a,a+n,value);