当前位置: 代码迷 >> 综合 >> ***1091. 六度空间
  详细解决方案

***1091. 六度空间

热度:0   发布时间:2023-12-06 11:22:56.0

题目:
**
在这里插入图片描述
代码:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 11111
using namespace std;
vector<int> a[maxn];
int x,y,n,m,ans,dis[maxn];
bool visited[maxn];
int main()
{
    cin>>n>>m;for(int i=1;i<=m;i++){
    cin>>x>>y;a[x].push_back(y);a[y].push_back(x);}for(int i=1;i<=n;i++){
    memset(visited,0,n+1);ans=0;queue<int> q;q.push(i);dis[i]=0;visited[i]=true;while (!q.empty()){
    int now=q.front();q.pop();if (dis[now]<=6) ans++;if (dis[now]==6) continue;for (auto to:a[now]){
    if (!visited[to]) {
    q.push(to);visited[to]=true;dis[to]=dis[now]+1;}}}//ansprintf("%d: %.2lf%%\n",i,(double)ans/n*100);}return 0;
}