Six dimensional space BFS

“ Six degrees of space ” Theory is also called “ Six degrees apart （Six Degrees of Separation）” theory . This theory can be explained as ：“ There will be no more than six people between you and any stranger , in other words , You can meet any stranger by five people at most .” Pictured 1 Shown .

“ Six degrees of space ” Although the theory is widely accepted , And it's getting more and more applications . But for decades , Trying to test this theory has always been the goal of many sociologists . But for historical reasons , Such research has too much limitation and difficulty . With modern people's contact mainly depends on the telephone 、 SMS 、 Wechat and instant messaging on the Internet , The first-hand data that can reflect social network relationships has gradually made “ Six degrees of space ” It is possible to test the theory .

If I give you a social network diagram , Please calculate each node according to “ Six degrees of space ” The percentage of theoretical nodes in the total number of nodes .

Input format :

Enter the first 1 Line gives two positive integers , Respectively represent the nodes of social network graph N（1<N≤10
​3
​​ , It means the number of people ）、 Number of edges M（≤33×N, It means the social relation coefficient ）. And then M Row correspondence M side , Each line gives a pair of positive integers , They are the numbers of the two nodes directly connected by the edge （ Node slave 1 To N Number ）.

Output format :

For each node, the distance between the output and the node is not more than 6 The percentage of the number of nodes in the total number of nodes , Accurate to the decimal point 2 position . One line per nodule , The format is “ Node number :（ Space ） percentage %”.

sample input :

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

sample output :

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%

————————————————————————————
The time limit is very long
There is no need to consider the time complexity
Thinking is also more violent ：
Traverse each point ,N Time bfs, however bfs Only a limited number of times , the reason being that 6 Limit of degree space ;
Not more than each time 6 There are a few of them
Then go back

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int n = 1e3 + 10;
vector<int> v[n];
int N;

double bfs(int k)
{
    
    queue<pair<int, int>> q;
    int dp[n] = {
    0};
    q.push({
    k, 0});
    dp[k] = 1;
    int cnt = 0;
    while (!q.empty())
    {
    
        auto x = q.front();
        q.pop();
        if (x.second >= 7)
            break;
        cnt++;
        for (auto &e : v[x.first])
            if (!dp[e])
            {
    
                dp[e] = 1;
                q.push({
    e, x.second + 1});
            }
    }
    return 1.0 * cnt / N * 100;
}
int main()
{
    
    int M, x, y;
    cin >> N >> M;
    while (M--)
    {
    
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (int i = 1; i <= N; i++)
    {
    
        printf("%d: %.2f%%\n", i, bfs(i));
    }
    return 0;
}