题目

答案

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
vector<int> vec[1001];
int vis[1001];

float bfs(int root)//按层遍历 
{
	queue<int> q;
	q.push(root);
	int level=0,cnt=0;
	int last=root;//last用来划分层 

	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		for(int i=0;i<vec[tmp].size();i++)
		if(vis[vec[tmp][i]]==0)
		{
			q.push(vec[tmp][i]);
			cnt++;
			vis[vec[tmp][i]]=1;
		}
		if(tmp==last)
		{
			level++;last=q.back();
		}
		if(level==6) break;
	}
	return cnt;
}

int main()
{
	int n,m;
	memset(vis,0,sizeof vis);
	cin>>n>>m;
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d: %.2f%\n",i,bfs(i)/n*100);
		memset(vis,0,sizeof vis);
	}
}

注意

1. level要在该层的所有节点遍历完后再加1
2. 取出队列的最后一个元素，使用的是q.back()