PTA 六度空间

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


图1 六度空间示意图

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

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

输入格式:

输入第1行给出两个正整数,分别表示社交网络图的结点数N(1<N≤103,表示人数)、边数M(≤33×N,表示社交关系数)。随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个结点的编号(节点从1到N编号)。

输出格式:

对每个结点输出与该结点距离不超过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>
typedef struct ArcNode* Arc;
struct ArcNode
{
    int adjvex;
    Arc next;
};
Arc graph[1005];
void init(int M);
int bfs(int);
void test(int);
void createNode(int v1,int v2)
{
    Arc newnode=(Arc)malloc(sizeof(struct ArcNode));
    newnode->next=NULL;
    newnode->adjvex=v2;
    if(graph[v1]==NULL)
    {
        graph[v1]=newnode;
    }
    else
    {
        Arc pre=graph[v1];
        Arc cur=pre->next;
        while(cur!=NULL)
        {
            pre=cur;
            cur=cur->next;
        }
        pre->next=newnode;
    }
    //
    Arc node=(Arc)malloc(sizeof(struct ArcNode));
    node->next=NULL;
    node->adjvex=v1;
    if(graph[v2]==NULL)
    {
        graph[v2]=node;
    }
    else
    {
        Arc pre=graph[v2];
        Arc cur=pre->next;
        while(cur!=NULL)
        {
            pre=cur;
            cur=cur->next;
        }
        pre->next=node;
    }
    //
    return;
}
int main()
{
    int N,M;
    scanf("%d%d",&N,&M);
    init(N);
    for(int i=0;i<M;i++)
    {
        int v1,v2;
        scanf("%d%d",&v1,&v2);
        createNode(v1,v2);
    }

    //
    for(int i=1;i<=N;i++)
    {
        float res=bfs(i);
        float rate=res/N;
        rate*=100;
        printf("%d: %.2f%%\n",i,rate);
    }
    //
    return 0;
}
void init(int N)
{
    for(int i=0;i<=N;i++)
    {
        graph[i]=NULL;
    }
    return;
}
int bfs(int vex)
{
    int cnt=0;
    int st[1005]={0};
    int queue[1005];
    int head=0,tail=0;
    queue[tail++]=vex;
    st[vex]=1;
    while(head<tail)
    {
        int v1=queue[head++];
        cnt++;
        Arc temp=graph[v1];
        if(st[v1]<7)
        while(temp!=NULL)
        {
            int v2=temp->adjvex;
            if(st[v2]!=0)
            {
                temp=temp->next;
                continue;
            }
            else
            {
            st[v2]=st[v1]+1;
            queue[tail++]=v2;
            temp=temp->next;
            }
        }
    }
    return cnt;
}
void test(int vex)
{
    Arc cur=graph[vex];
    while(cur!=NULL)
    {
        printf("%d ",cur->adjvex);
        cur=cur->next;
    }
    printf("\n");
    return;
}

本题应该使用邻接表作为存储结构,邻接矩阵的时间复杂度为n^2会超时。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/180295.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Springboot+vue的新冠病毒密接者跟踪系统(有报告)。Javaee项目,springboot vue前后端分离项目

演示视频&#xff1a; Springbootvue的新冠病毒密接者跟踪系统(有报告)。Javaee项目&#xff0c;springboot vue前后端分离项目 项目介绍&#xff1a; 本文设计了一个基于Springbootvue的新冠病毒密接者跟踪系统&#xff0c;采用M&#xff08;model&#xff09;V&#xff08;v…

【实用】PPT没几页内存很大怎么解决

PPT页数很少但导出内存很大解决方法 1.打开ppt点击左上角 “文件”—“选项” 2.对话框选择 “常规与保存” &#xff08;1&#xff09;如果想要文件特别小时可 取消勾选 “将字体嵌入文件” &#xff08;2&#xff09;文件大小适中 可选择第一个选项 “仅最入文档中所用的字…

【数组栈】实现

目录 栈的概念及其结构 栈的实现 数组栈 链式栈 栈的常见接口实现 主函数Test.c 头文件&函数声明Stack.h 头文件 函数声明 函数实现Stack.c 初始化SLInit 扩容Createcapacity 压栈STPush 出栈STPop 栈顶元素STTop 判断栈是否为空STempty 栈内元素个数STSzi…

ABB机 器 人 操 作 培 训

目 录 1 培训手册介绍 ---------------------------------------------2 2 系统安全与环境保护 ---------------------------------------------3 3 机器人综述 ---------------------------------------------5 4 机器人示教 --------------------------------------------12…

普通平衡树

题意&#xff1a;略&#xff0c;题中较清晰。 用二叉查找树来存储数据&#xff0c;为了增加效率&#xff0c;尽量使左子树和右子树的深度差不超过一&#xff0c;这样可以时间控制在logn&#xff0c;效率比较高。 右旋和左旋&#xff0c;目的是为了维护二叉树的操作&#xff0…

CSGO搬砖项目全面讲解 ,CSGO搬砖注意事项

Steam/CSGO游戏搬砖全套操作流程之如何选品&#xff08;第二课&#xff09; 一个游戏只要能搬&#xff0c;只要体量不够大&#xff0c;很快就会货币价格暴跌&#xff0c;直接凉凉。市面上的能稳定手动搬砖的游戏越来越少。所以对于兼职赚点外快的散人搬砖党来说&#xff0c;找一…

【Vue入门篇】基础篇—Vue指令,Vue生命周期

&#x1f38a;专栏【JavaSE】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f354;Vue概述&#x1f384;快速入门&#x1f33a;Vue指令⭐v-…

微信小程序登录获取不到头像和昵称解决办法

微信小程序登录获取不到头像和昵称主要原因是&#xff1a;小程序wx.getUserProfile接口被收回&#xff01; 大家可以按照文档操作↓ PS&#xff1a; 针对小程序wx.getUserProfile接口将被收回后做出的授权调整 小程序文档中提出的调整说明 对于此次变化&#xff0c;现将小程…

如何满足BMW EDI项目的PKT需求?

近期宝马BMW&#xff08;以下简称BMW&#xff09;在其部分供应商之间试点推进PKT项目&#xff0c;BMW为什么要启动 PKT 计划呢&#xff1f; 业务系统全面升级统一全球所有宝马工厂的流程 宝马内部的物流供货流程 近期BMW PKT需求主要针对其内部物流供货流程展开&#xff1a; …

Android : Spinner(列表选项框) + BaseAdapter -简单应用

​​容器与适配器&#xff1a;​​​​​ http://t.csdnimg.cn/ZfAJ7 示例图&#xff1a; 实体类 Demo.java package com.example.mygridviewadapter.entity;public class Demo {private String text;private int img;public Demo(String text, int img) {this.text…

QQ怎么备份聊天记录?3个方法教你快速备份!

QQ聊天记录作为用户和亲人、好友以及同事之间沟通的凭证&#xff0c;可以帮助我们回忆起过去的交流内容。如果我们不小心误删了QQ聊天记录或者更换了新手机&#xff0c;那么这时候就需要备份聊天记录。qq怎么备份聊天记录呢&#xff1f;本文将介绍3个简单方法&#xff0c;帮助您…

Oracle-客户端连接报错ORA-12545问题

问题背景: 用户在客户端服务器通过sqlplus通过scan ip登陆访问数据库时&#xff0c;偶尔会出现连接报错ORA-12545: Connect failed because target host or object does not exist的情况。 问题分析&#xff1a; 首先&#xff0c;登陆到连接有问题的客户端数据库上&#xff0c;…

va-Q-tec实现温度敏感产品运输过程质量控制温控无忧

摘要&#xff1a;温度敏感产品运输对供应链全流程的温度质量要求较高&#xff0c;往往需要借助特殊的温湿度监测技术产品。va-Q-tec与虹科Comet合作&#xff0c;采用虹科Comet的U系列温度记录仪&#xff0c;为集装箱运输过程提供完整的温控包装解决方案。 一、客户背景 va-Q-…

算法通关村第十二关-白银挑战字符串经典题目

大家好我是苏麟 , 今天带来字符串相关的题目 . 大纲 反转问题字符串反转K个一组反转仅仅反转字母反转字符串中的单词 反转问题 字符串反转 描述 : 编写一个函数&#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 s的形式给出。 题目 : LeetCode 344. 反转…

【PPspliT】ppt转pdf-保留过渡动画

网址 http://www.maxonthenet.altervista.org/ppsplit.php 下载安装 使用 再次打开ppt&#xff0c;就能在上方的选项栏里头看到了&#xff1a;

【Unity】接入MAX聚合广告SDK Applovin + GoogleAdmob

版本&#xff1a; Unity&#xff1a;2019.4.35f1gradle plugin: 4.2.0 &#xff08;实际要7.0 对应build_tools:34.0.0) gradle: 6.7.1 &#xff08;实际要7.0 对应build_tools:34.0.0) jdk: 1.8.0_241build_tools: 34.0.0 ndk: android-ndk-r19 文档&#xff1a; 6.0.1(Andro…

使用宝塔安装Alist

废话不多说&#xff0c;直接上教程&#xff0c;根据我的步骤一步一步来&#xff0c;肯定可以成功&#xff01; 我这边使用一键安装的时候&#xff0c;一致报错&#xff0c;提示证书过期&#xff0c;无奈我就开始了手动安装&#xff0c;下面的教程也是手动安装的教程 首先&…

RabbitMQ安装说明

注意: 本次安装以 CentOS 7为例 1、 准备软件 erlang 18.3 1.el7.centos.x86_64.rpm socat 1.7.3.2 5.el7.lux.x86_64.rpm rabbitmq server 3.6.5 1.noarch.rpm 2、安装Erlang rpm -ivh erlang-18.3-1.el7.centos.x86_64.rpm 3.、安装RabbitMQ 安装 rpm -ivh socat-1.7.3.2-…

码云 -- 本地代码上传到码云

1. 在码云上创建远程仓库 复制远程仓库地址 2. 在本地代码上创建 git 仓库 在本地代码文件夹上&#xff0c;打开git 命令窗口 输入初始化命令&#xff0c;创建 git 仓库 git init3. 给 git 仓库添加远程仓库 继续输入 git 命令 git remote add origin 远程仓库地址4. 按 git 的…

提升性能测试效率:JMeter中的用户自定义变量!

前言 在测试过程中&#xff0c;我们经常会碰到测试服务地址有改动的情况&#xff0c;为了方便&#xff0c;我们会把访问地址参数化&#xff0c;当访问地址变化了&#xff0c;我们只需要把参数对应的值改动一下就可以了。 一&#xff1a;添加配置元件-用户定义的变量&#xff…