欢迎登录北京林业大学OJ系统
http://www.bjfuacm.com
274六度空间理论
描述
“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入
多组数据，每组数据m+1行。第一行有两个数字n和m，代表有n个人和m组朋友关系。n个人的编号为1到n。第二行到第m+1行每行包括两个数字a和b，代表这两个人互相认识。当n和m都等于0时，输入结束。
输出
每组数据输出n行，对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。
输入样例 1
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
9 10
0 0
输出样例 1
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%
1: 70.00%
2: 80.00%
3: 80.00%
4: 80.00%
5: 80.00%
6: 80.00%
7: 80.00%
8: 70.00%
9: 20.00%
10: 20.00%
#include<iostream>using namespace std;#define OK 0#define ERROR -1#define MAX 100typedef struct LNode{int data;struct LNode *next;}LNode,*LinkList;typedef struct{LinkList V[MAX];int vexnum; int arcnum;int visit[MAX]; int Queue[MAX];}ALGragh;int CreateUDN(ALGragh &G,int vexnum,int arcnum){G.vexnum=vexnum;G.arcnum=arcnum;if(G.vexnum>MAX) return ERROR; for(int i=1;i<=vexnum;i++){G.V[i]=new LNode;G.V[i]->data=i;G.V[i]->next=NULL;} while(arcnum--){ int x,y;cin>>x>>y; LinkList p=new LNode;p->data=y;p->next=G.V[x]->next; G.V[x]->next=p; LinkList q=new LNode;q->data=x;q->next=G.V[y]->next;G.V[y]->next=q;} return OK;}void SixDegree_BFS(ALGragh G){for(int j=1;j<=G.vexnum;j++){int Visit_Num=1;int front=0,rear=0,last=0;for(int i=1;i<=G.vexnum;i++)G.visit[i]=0;G.Queue[0]=j;G.visit[j]=1;int js=0;while(front<=last){LinkList p=G.V[G.Queue[front++]]->next;while(p){if(!G.visit[p->data]){G.visit[p->data]=1;Visit_Num++;G.Queue[++rear]=p->data;}p=p->next;}if(front>last){last=rear;js++;if(js==6)break;}}printf("%d: %.2f%%n",j,100.0*Visit_Num/G.vexnum);}}int main(){int n,m;while(cin>>n>>m&&n!=0&&m!=0){ALGragh G;CreateUDN(G,n,m);SixDegree_BFS(G);}return 0;}