六度空間（廣度優先搜尋）

題目在https://pintia.cn/problem-sets/15/problems/715這裡

我就不放了

你可能不知道什麼事廣度優先搜尋，沒有關系。

廣度優先搜尋使用隊列（queue）來實作，整個過程也可以看做一個倒立的樹形：

1、把根節點放到隊列的末尾。

2、每次從隊列的頭部取出一個元素，檢視這個元素所有的下一級元素，把它們放到隊列的末尾。并把這個元素記為它下一級元素的前驅。

3、找到所要找的元素時結束程式。

4、如果周遊整個樹還沒有找到，結束程式。

廢話不說了。

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int steps;
	int lu[3300];
	int cnt;
}a[1010];
int n,m,x,y,cnt1,vit[1010];
int main()
{
	queue<node> p;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		a[x].lu[++a[x].cnt]=y;
		a[y].lu[++a[y].cnt]=x;
	}
	for(int i=1;i<=n;i++)
	{
		memset(vit,0,sizeof(vit));
		cnt1=0;
		for(int j=1;j<=n;j++)
		a[j].steps=0;
		p.push(a[i]);
		vit[i]=1;
		while(p.empty()==0)
		{
			node b=p.front();
			p.pop();
			if(b.steps>6)
			continue;
			cnt1++;
			for(int j=1;j<=b.cnt;j++)
			{
				if(vit[b.lu[j]]==0)
				{
					a[b.lu[j]].steps=b.steps+1;
					p.push(a[b.lu[j]]);
					vit[b.lu[j]]=1;
				}
			}
		}
		printf("%d: %.2lf%%\n",i,cnt1*1.0/n*100);
	}
}