“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。
图1 六度空间示意图
“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式:输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤104，表示人数）、边数M（≤33×N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。
输出格式:对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。
输入样例: 10 91 22 33 44 55 66 77 88 99 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% 运行效果 CaseHintResultRun TimeMemory0sample 简单一条链Accepted2 ms384 KB1不连通Accepted2 ms416 KB2一般图Accepted3 ms416 KB3最小N和MAccepted2 ms416 KB4最大N和MAccepted497 ms2592 KB程序 #include<iostream>using namespace std;#define MaxVertexNum 10000//最多顶点（结点）数#define MaxDistance 6//BFS广度优先搜索允许遍历到的层数#define DefaultWeight 1//无边的权重要求，则默认为1#define QERROR 0//队列发生错误typedef int Vertex;//用顶点下标表示顶点typedef int WeightType;//边的权重//定义图的边typedef struct ENode *PtrToENode;struct ENode{ Vertex V1, V2; //有向边<V1,V2> WeightType Weight;//权重};typedef PtrToENode Edge;//邻接点的定义typedef struct AdjVNode *PtrToAdjVNode;struct AdjVNode{ Vertex AdjV; //邻接点的下标 WeightType Weight;//边权重 PtrToAdjVNode Next;//指向下一个邻接点的指针};//顶点表头的定义typedef struct Vnode{ PtrToAdjVNode FirstEdge;//变表头指针} AdjList[MaxVertexNum];//AdjList是邻接表类型//图结点的定义typedef struct GNode *PtrToGNode;struct GNode{ int Nv;//顶点数 int Ne;//边数 bool *visited;//顶点被访问状态数组的指针 AdjList G;//邻接表};typedef PtrToGNode LGraph;//以邻接表方式存储的图类型//队列的结点定义typedef struct Node *PtrToNode;struct Node{ Vertex Data;//队列结点存储的数据 PtrToNode Next;//指向下一个队列结点的指针};typedef PtrToNode Position;//队列的定义struct QNode{ Position Front, Rear;//队列的头结点和尾结点 int MaxSize;//队列的最jddsy存储大小};typedef struct QNode *Queue;//以链表的形式实现队列LGraph CreateGraph(int Nv);void InsertEdge(LGraph Graph, Edge E);void BFSToSix(LGraph Graph);int BFS(LGraph Graph, Vertex v);Queue CreateQueue(int MaxSize);bool QIsEmpty(Queue Q);Vertex DeleteQ(Queue Q);void AddQ(Queue Q, Vertex v);int main(){ /* //测试用例 int N; int M; N = 10; LGraph Graph; Graph = CreateGraph(N); M = 9; int V1Arr[M] = {1,2,3,4,5,6,7,8,9}; int V2Arr[M] = {2,3,4,5,6,7,8,9,10}; Edge E; E = new ENode; for(int e=0; e<M; e++){ E->V1 = V1Arr[e]; E->V2 = V2Arr[e]; E->Weight = DefaultWeight; InsertEdge(Graph, E); } BFSToSix(Graph); */ //正式应用 int N, M; LGraph Graph; Edge E; cin >> N; //输入结点总数 Graph = CreateGraph(N); //创建无边图 cin >> M; //输入边的个数 E = new ENode; for(int i=0; i<M; i++){ cin >> E->V1; cin >> E->V2; E->Weight = DefaultWeight; InsertEdge(Graph, E); } BFSToSix(Graph);//六度分隔理论模拟 return 0;}void BFSToSix(LGraph Graph){ int SixVertexNum; float percent; if(Graph->Nv != 0){ for(Vertex v=1; v<Graph->Nv; v++){ //在六步内可遍历到的顶点数（其中还要加上结点本身） SixVertexNum = BFS(Graph, v) +1; //在六步内可遍历到的顶点数占总结点数的百分比（结点从1开始，需要减去0这个无用结点） percent = float(SixVertexNum)/float(Graph->Nv-1); printf("%d: %.2f%n", v, percent*100); //清空结点被遍历状态 for(int i=0; i<Graph->Nv; i++) Graph->visited[i] = false; } }}int BFS(LGraph Graph, Vertex v){ PtrToAdjVNode w; int D = 0; int SixVertexNum = 0; Queue Q; Q = CreateQueue(MaxVertexNum);//创建队列 Graph->visited[v] = true; AddQ(Q, v); AddQ(Q, 0);//插入队列中的0，用于表示新的一层的开始 ++D;//所在的层数 while(!QIsEmpty(Q)){ v = DeleteQ(Q); if(v == 0 && D >= MaxDistance) break; //表示层数已超过6 if(v == 0 && D < MaxDistance){//层数还未超过6 AddQ(Q, 0); ++D; continue; } for(w=Graph->G[v].FirstEdge; w != NULL; w=w->Next){ if(!Graph->visited[w->AdjV]){ Graph->visited[w->AdjV] = true; AddQ(Q, w->AdjV); ++SixVertexNum; } } } return SixVertexNum;}void InsertEdge(LGraph Graph, Edge E){ PtrToAdjVNode NewNode; ++Graph->Ne; //插入<V1,V2> NewNode = new AdjVNode; NewNode->AdjV = E->V2; NewNode->Weight = E->Weight; NewNode->Next = Graph->G[E->V1].FirstEdge; Graph->G[E->V1].FirstEdge = NewNode; //插入<V2,V1> NewNode = new AdjVNode; NewNode->AdjV = E->V1; NewNode->Weight = E->Weight; NewNode->Next = Graph->G[E->V2].FirstEdge; Graph->G[E->V2].FirstEdge = NewNode;}LGraph CreateGraph(int N){ LGraph Graph; Graph = new GNode; Graph->Nv = N+1; //结点从1开始 Graph->Ne = 0; Graph->visited = new bool [N+1]; for(int i=1; i<Graph->Nv; i++) Graph->visited[i] = false; for(int v=1; v<Graph->Nv; v++) Graph->G[v].FirstEdge = NULL; return Graph;}Queue CreateQueue(int MaxSize){ Queue Q; Q = new QNode; Q->Front = Q->Rear = NULL; Q->MaxSize = MaxSize; return Q;}bool QIsEmpty(Queue Q){ return (Q->Front == NULL);}void AddQ(Queue Q, Vertex v){ Position NewNode; NewNode = new Node; NewNode->Data = v; NewNode->Next = NULL; if(QIsEmpty(Q)){ Q->Front = NewNode; Q->Rear = NewNode; } else{ Q->Rear->Next = NewNode; Q->Rear = NewNode; }}Vertex DeleteQ(Queue Q){ Position FrontNode; Vertex FrontData; if( QIsEmpty(Q)){ return QERROR; } else{ FrontNode = Q->Front; if( Q->Front == Q->Rear) Q->Front = Q->Rear = NULL; else Q->Front = Q->Front->Next; FrontData = FrontNode->Data; delete FrontNode; return FrontData; }}