|
#2
书生牛犊2016-06-28 00:00
交流：
 程序代码：#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; } |
“六度空间”理论又称作“六度分隔（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 <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 ;
}