“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。


图1 六度空间示意图
“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入格式:

输入第1行给出两个正整数，分别表示社交网络图的结点数NN（1<N\le 10^41<N≤10
4
 ，表示人数）、边数MM（\le 33\times N≤33×N，表示社交关系数）。随后的MM行对应MM条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到NN编号）。

输出格式:

对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。

输入样例:

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 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%

#include <stdio.h>
#include <stdlib.h>
int N,M ; //节点数，边数
int graph[10001][10001] ; //顶点从1开始编号
int count  ;
int visited[10001] ;

typedef struct quedeNode
{
    int rear ;
    int front ;
    int data[ 10000 ] ;
} quede ;

void initQ( quede* Q )
{
    Q->rear = 0  ;
    Q->front = 0 ;
}


void addQ( quede* Q , int item)
{
    Q->data[ Q->rear ] = item ;
    Q->rear++ ;
}


int  deleteQ( quede* Q  )
{
    int i ;
    i = Q->front ;
    Q->front++   ;
    return Q->data[ i ] ;
}


int isEmptyQ( quede* Q )
{
    if( Q->front == Q->rear )
        return 1 ;
    else return 0 ;
}


void BFS( int curV, quede* Q )
{
    int last , tail ;
    int i,v ;
    int level = 0 ;

    addQ( Q , curV ) ;
    last = curV ;
    visited[ curV ] = 1 ;
    while( !isEmptyQ( Q ) )
    {
        v = deleteQ( Q ) ;    
        
        for(i=1; i<=N; i++)
        {
            if( graph[v][i]==1 && visited[i]==0 )//有边连接且未被访问
            {    
                tail = i ;//保存最后一个入队的结点
                count++ ;        
                addQ( Q , i ) ;
                visited[ i ] = 1 ;     //入队顶点标记    
            }
        }

        //考虑换个位置
        if( v==last )//上一层最后一个入队的顶点出队则层数加1
        {
            last = tail ;
            level++ ;    //层数加1
        }

        if( level==6 ) break ;
    }
}


void six( )
{
    int i,j ;
    double percent ;
    quede* Q ;

    Q = (quede*)malloc( sizeof( quede ) ) ;

    
    for( i=1; i<=N; i++ )
    {    
        for( j=1; j<=N; j++ )
            visited[ j ] = 0 ;
        initQ( Q );
        count = 1 ;
        BFS( i , Q ) ;
        
        percent = (double)count/N ;//count转换为浮点数计算除法
        printf( "%d: %.2f%%\n",i,percent*100 ) ;
    }
    
}






int main(   )
{
    int i,j ;
    int v1,v2 ;

    scanf("%d%d",&N,&M);

    for(i=1; i<=N; i++)
        for(j=1; j<=N; j++)
            graph[i][j] = 0 ;



    for( i=1 ; i<=M; i++ )
    {
        scanf("%d%d" , &v1,&v2);
        graph[v1][v2] = graph[v2][v1] = 1 ;
    }

    six( ) ;
    return 0 ;
}

交流：

#include <stdio.h>
#include <stdlib.h>
#define NUM 10001

/*
时间     结果     得分     题目     编译器     用时（ms）     内存（MB）     用户
2016-04-02 17:51     答案正确     30     06-图3     gcc     790     3     569985011
测试点结果 测试点     结果     得分/满分     用时（ms）     内存（MB）     要点提示
测试点1     答案正确     18/18     1     1     sample 简单一条链
测试点2     答案正确     3/3     1     1     不连通
测试点3     答案正确     3/3     2     1     一般图
测试点4     答案正确     3/3     2     1     最小N和M
测试点5     答案正确     3/3     790     3     最大N和M
*/
typedef struct LNode *Vertex;
struct LNode {
    int Data;
    Vertex Next;
};
Vertex CreatV(int);

void Print(Vertex num,int n);
void InsertV(Vertex,int);
int BFS(Vertex,int);
int Connected[10001],Visited[10001],N;

int main() {
    int M;
    scanf("%d%d",&N,&M);
    int from,to;
    Vertex V=CreatV(N+1);
    for(int i=0; i<M; i++) {
        scanf("%d%d",&from,&to);
        InsertV(&V[from],to);
        InsertV(&V[to],from);
    }
     for(int i=0;i<=N;i++)Visited[i]=0;
    int cnt;
    for(int i=1; i<=N; i++) {
        printf("%d: ",i);
        cnt=BFS(V,i);
        printf("%.2f%%\n",cnt*100.0/N);
    }
}
int BFS(Vertex V,int X) {
    Connected[0]=X;
    Visited[X]=X;
    int right=1,left=0,cen=6,pause=0;
    while(left<right) {
        Vertex temp=V[Connected[left]].Next;
        for(;temp&&right<N;temp=temp->Next) {
            if(Visited[temp->Data]!=X){
                Connected[right++]=temp->Data ;
                Visited[temp->Data ]=X;
            }
        }
        if(left++==pause){
            if(!--cen)break;
            pause=right-1;
        }
   

    }
    return right;
}
Vertex CreatV(int num) {
    Vertex V=(Vertex)malloc(sizeof(struct LNode)*num);
    for(int i=1; i<num; i++) {
        V[i].Next=NULL;
        V[i].Data=i;
    }
    return V;
}
void InsertV(Vertex V,int X) {

    Vertex NewV=(Vertex)malloc(sizeof(struct LNode));
    NewV->Data=X;
    NewV->Next=V->Next ;
    V->Next =NewV;
}