当前位置: 首页 > news >正文

浙大数据结构慕课课后题(06-图3 六度空间)

题目要求:

输入格式:

输入第1行给出两个正整数,分别表示社交网络图的结点数N1<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<bits/stdc++.h>
using namespace std;const int MAX_N = 1005; 
vector<vector<int>> sds;  //二维动态数组 
bool vis[MAX_N];int BFS(int v){int count = 1,level = 0,last = v,tail;queue<int> q;q.push(v);vis[v] = true;while(!q.empty()){int u = q.front();q.pop();for(int w : sds[u]){if(!vis[w]){vis[w] = true;q.push(w); count++;tail = w;		}	} if(u == last){level++; last = tail;}if(level == 6) break;}return count;
}int main(){int N,M;cin>>N>>M;sds.resize(N+1);           //动态设置sds数组的大小 fill(vis,vis + N + 1,false);   //初始化vis数组 for(int i = 0; i < M; i++){int u,v;cin>>u>>v;sds[u].push_back(v);sds[v].push_back(u);}	for(int i = 1; i <= N; i++){int count = BFS(i);	      //BFS函数的返回值即为符合要求的结点数目 double ans = 100.0*count/N;printf("%d: %.2f%%\n", i, ans);		fill(vis,vis+N+1,false);    //初始化vis数组 }return 0;
}

总结: 

1. vector二维数组的声名格式有两种:假设数组名为sds。

(1)如果我们提前知道了数组的大小可以这样定义:

MAX_N=1005;

vector<int> sds[MAX_N];

(2)如果不知道数组大小,又需要全局声名就要在main函数外这样定义: 

vector<vector<int>> sds;

然后在main函数里面这样确定数组大小:

int main(){

...

cin>>N;

sds.resize(N);        //resize()函数

...

}

2.在取百分号时,乘数100要写成100.0  虽然在代码中 用了一个double类型的数据来接收计算结果,但是如果写的是(*100)那么编译器会先进行整数乘法,再用浮点数来存取,精度已经损失了,测试点中有两个例子卡的就是这个地方(别问我怎么知道的@_@)。

3.此题的思路比较巧妙,用一个last变量来存储一层的最后一个元素,如果这个元素被弹出,则说明这一层已经遍历完成,从而实现对层数的控制,当层数>=6时,函数终止。

4.题目内容说完了,下面是关于dev编译器,我用的是比较老的devc++,因为看重了它的简洁,但是如果要用到一些c++11的特性,比如本题中的foreach循环会报错,要在这个地方设置一下。

找到编译器选项,加入红框里的语句即可。

 

 

相关文章:

浙大数据结构慕课课后题(06-图3 六度空间)

题目要求&#xff1a; 输入格式: 输入第1行给出两个正整数&#xff0c;分别表示社交网络图的结点数N&#xff08;1<N≤103&#xff0c;表示人数&#xff09;、边数M&#xff08;≤33N&#xff0c;表示社交关系数&#xff09;。随后的M行对应M条边&#xff0c;每行给出一对正…...

Windows File Recovery卡在99%怎么解决?实用指南!

为什么会出现“Windows File Recovery卡在99%”的问题&#xff1f; Windows File Recovery&#xff08;Windows文件恢复&#xff09;是微软设计的命令行应用程序。它可以帮助用户从健康/损坏/格式化的存储设备中恢复已删除/丢失的文件。 通过输入相关命令&#xff0c;设置源/…...

数据结构之数组

写在前面 看下数组。 1&#xff1a;巴拉巴拉 数组是一种线性数据结构&#xff0c;使用连续的内存空间来存储数据&#xff0c;存储的数据要求有相同的数据类型&#xff0c;并且每个元素占用的内存空间相同。获取元素速度非常快&#xff0c;为O(1)常量时间复杂度&#xff0c;所…...

springboot集成sensitive-word实现敏感词过滤

文章目录 敏感词过滤方案一&#xff1a;正则表达式方案二&#xff1a;基于DFA算法的敏感词过滤工具框架-sensitive-wordspringboot集成sensitive-word步骤一&#xff1a;引入pom步骤二&#xff1a;自定义配置步骤三&#xff1a;自定义敏感词白名单步骤四&#xff1a;核心方法测…...

C++ 之动手写 Reactor 服务器模型(一):网络编程基础复习总结

基础 IP 地址可以在网络环境中唯一标识一台主机。 端口号可以在主机中唯一标识一个进程。 所以在网络环境中唯一标识一个进程可以使用 IP 地址与端口号 Port 。 字节序 TCP/IP协议规定&#xff0c;网络数据流应采用大端字节序。 大端&#xff1a;低地址存高位&#xff0c…...

qt 在vs2022 报错记录

1&#xff0c;qt.network.ssl: QSslSocket::connectToHostEncrypted: TLS initialization failed 需要把SSL 相关的库加入进去&#xff0c;如ssleay32.dll&#xff0c;libeay32.dll。 2&#xff0c;在一个文件中已定义&#xff0c;编译器在链接时&#xff0c;在多处报 已在.*…...

【人工智能】TensorFlow和机器学习概述

一、TensorFlow概述 TensorFlow是由Google Brain团队开发的开源机器学习库&#xff0c;用于各种复杂的数学计算&#xff0c;特别是在深度学习领域。以下是对TensorFlow的详细概述&#xff1a; 1. 核心概念 张量&#xff08;Tensor&#xff09;&#xff1a;TensorFlow中的基本…...

SQLALchemy 的介绍

SQLALchemy 的介绍 基本概述主要特点使用场景安装与配置安装 SQLAlchemy配置 SQLAlchemy示例&#xff1a;使用 SQLite 数据库连接到其他数据库 结论 总结 SQLAlchemy是Python编程语言下的一款开源软件&#xff0c;它提供了SQL工具包及对象关系映射&#xff08;ORM&#xff09;工…...

Java虚拟机:运行时内存结构

大家好&#xff0c;我是栗筝i&#xff0c;这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 035 篇文章&#xff0c;在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验&#xff0c;并希望进…...

微信小程序子组件调用父组件的方法

来源&#xff1a;通义千文2.5 步骤 1: 定义父组件中的方法 首先&#xff0c;在父组件中定义一个方法&#xff08;如 handleClick&#xff09;&#xff0c;并准备一个用于接收子组件传来的数据的方法。 父组件&#xff08;Parent.wxml&#xff09; html<!-- parent.wxml …...

【数据结构】TreeMap和TreeSet

目录 前言TreeMap实现的接口内部类常用方法 TreeSet实现的接口常用方法 前言 Map和set是一种专门用来进行搜索的容器或者数据结构&#xff0c;其搜索的效率与其具体的实例化子类有关。 一般把搜索的数据称为关键字&#xff08;Key&#xff09;&#xff0c; 和关键字对应的称为…...

前端react集成OIDC

文章目录 OpenID Connect (OIDC)3种 授权模式 【服务端】express 集成OIDC【前端】react 集成OIDCoidc-client-js库 原生集成react-oidc-context 库非组件获取user信息 OAuth 2.0 协议主要用于资源授权。 OpenID Connect (OIDC) https://openid.net/specs/openid-connect-core…...

JavaWeb—XML_Tomcat10_HTTP

一、XML XML是EXtensible MarkupLanguage的缩写&#xff0c;翻译过来就是可扩展标记语言。所以很明显&#xff0c;XML和HTML一样都是标记语言&#xff0c;也就是说它们的基本语法都是标签。 可扩展:三个字表面上的意思是XML允许自定义格式。但这不代表你可以随便写; 在XML基…...

中介者模式在Java中的实现:设计模式精解

中介者模式在Java中的实现&#xff1a;设计模式精解 中介者模式&#xff08;Mediator Pattern&#xff09;是一种行为型设计模式&#xff0c;用于定义一个中介者对象&#xff0c;以封装一系列对象之间的交互&#xff0c;从而使对象之间的交互不再直接发生&#xff0c;减少了系…...

PyQt编程快速上手

Python GUI安装 GUI就是图形用户界面的意思&#xff0c;在Python中使用PyQt可以快速搭建自己的应用&#xff0c;使得自己的程序看上去更加高大上&#xff0c;学会GUI编程可以使得自己的软件有可视化的结果。 如果你想用Python快速制作界面&#xff0c;可以安装PyQt&#xff1a…...

Docker Swarm管理

Docker Swarm管理 前置知识点 Docker Swarm 是 Docker 公司 2014年出品的基于 Docker 的集群管理调度工具&#xff0c;能够将多台主机构建成一个Docker集群&#xff0c;并结合Overlay网络实现容器调度的互访 用户可以只通过 Swarm API 来管理多个主机上的 Docker Swarm 群集包…...

Python | Leetcode Python题解之第335题路径交叉

题目&#xff1a; 题解&#xff1a; class Solution:def isSelfCrossing(self, distance: List[int]) -> bool:n len(distance)# 处理第 1 种情况i 0while i < n and (i < 2 or distance[i] > distance[i - 2]):i 1if i n:return False# 处理第 j 次移动的情况…...

Ubuntu视频工具

1. VLC VLC Media Player&#xff08;VLC多媒体播放器&#xff09;&#xff0c;最初命名为VideoLAN客户端&#xff0c;是VideoLAN品牌产品&#xff0c;是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式&#xff0c;并支持DVD影音光盘&#xff0c;VCD影音光…...

HBase snapshot+replication 测试

一、背景 画像标签服务&#xff08;CDP&#xff09;是核心服务&#xff0c;被公司其他系统如现金、电商、风控等核心业务调用。异常的话&#xff0c;影响范围大。 二、目标 存量数据测试通过 snapshot 迁移。增量数据测试通过 replication 同步。 三、测试 方案二测试&#x…...

代码随想录算法训练营第四十一天|图论基础、深度优先搜索理论基础、98. 所有可达路径、797. 所有可能的路径

图论基础 图的种类&#xff1a;有向图 和 无向图&#xff0c;加权有向图&#xff0c; 加权无向图 无向图中有几条边连接该节点&#xff0c;该节点就有几度。 在有向图中&#xff0c;每个节点有出度和入度。出度&#xff1a;从该节点出发的边的个数。入度&#xff1a;指向该节…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...