图的深度遍历

2023-11-16

题目描述

请定一个无向图,顶点编号从0到n-1,用深度优先搜索(DFS),遍历并输出。遍历时,先遍历节点编号小的。

输入

输入第一行为整数n(0 < n < 100),表示数据的组数。 对于每组数据,第一行是两个整数k,m(0 < k < 100,0 < m < k*k),表示有m条边,k个顶点。 下面的m行,每行是空格隔开的两个整数u,v,表示一条连接u,v顶点的无向边。

输出

输出有n行,对应n组输出,每行为用空格隔开的k个整数,对应一组数据,表示DFS的遍历结果。

示例输入

1
4 4
0 1
0 2
0 3
2 3

示例输出

0 1 2 3
 1 #include <stdio.h>
 2 #include <string.h>
 3 int p[101][101];//标记边
 4 int o[101];//标记点
 5 int num[101];//存遍历完的点
 6 int z;
 7 //dfs算法
 8 void dfs(int k,int v)
 9 {
10     int j;
11     o[v] = 1;
12     num[z++] = v;
13     for(j = 0;j <= k-1;j ++)
14     {
15         if(p[v][j] == 1 && o[j] == 0)
16         {
17             dfs(k,j);
18         }
19     }
20 }
21 
22 int main()
23 {
24     int n,k,m,u,v,i,j,t;
25     scanf("%d",&n);
26     while(n--)
27     {
28         memset(p,0,sizeof(p));
29         memset(o,0,sizeof(o));
30         memset(num,0,sizeof(num));
31         scanf("%d%d",&k,&m);
32         z = 0;
33         t = 0;
34         for(i=1;i<=m;i++)
35         {
36             scanf("%d%d",&u,&v);
37             p[v][u]=1;
38             p[u][v]=1;
39         }
40         for(i=0;i<=k-1;i++)
41         {
42             for(j=0;j<=k-1;j++)
43             {
44                 if(p[i][j]==1)
45                 {
46                     dfs(k,i);
47                     t = 1;
48                     break;
49                 }
50             }
51             if(t) break;
52         }
53         for(i=0;i<=z-1;i++)
54         {
55             if(i!=z-1)
56             printf("%d ",num[i]);
57             else
58             printf("%d\n",num[i]);
59         }
60     }
61 }
View Code

 

转载于:https://www.cnblogs.com/sdutmyj/p/3225265.html

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

图的深度遍历 的相关文章

  • 五大常用经典算法

    五大常用算法之一 分治算法 一 基本概念 在计算机科学中 分治法是一种很重要的算法 字面上的解释是 分而治之 就是把一个复杂的问题分成两个或更多的相同或相似的子问题 再把子问题分成更小的子问题 直到最后子问题可以简单的直接求解 原问题的解即
  • C语言/C++实现栈操作

    一 栈的概念 栈是一种常用的数据结构 它遵循先入后出 Last In First Out LIFO 的原则 栈的操作只在栈的一端进行 该端被称为栈顶 而另一端称为栈底 栈的基本操作包括压栈 入栈 push 和弹栈 出栈 pop 分别用于将元
  • 以OpenGL/ES视角介绍gfx-hal(Vulkan) Shader/Program接口使用

    文档列表见 Rust 移动端跨平台复杂图形渲染项目开发系列总结 目录 背景 The right way to tackle this in Vulkan is to use resource descriptors A descriptor
  • LeetCode83: 删除排序链表中的重复元素

    给定一个已排序的链表的头 head 删除所有重复的元素 使每个元素只出现一次 返回 已排序的链表 示例 1 输入 head 1 1 2 输出 1 2 示例 2 输入 head 1 1 2 3 3 输出 1 2 3 提示 链表中节点数目在范围
  • Qt——用于表格QTableView的模型

    如果想使用表格来呈现数据 Qt提供了一个方便的部件QTableWidget 但是直接用它实现一些功能可能比较困难 这里将介绍一种强大 灵活的方式来操作表格 一 模型 视图架构 在这个架构中 模型用于存储数据 视图用于呈现数据 除此之外 还有
  • PCL—低层次视觉—点云分割(RanSaC)

    点云分割 点云分割可谓点云处理的精髓 也是三维图像相对二维图像最大优势的体现 不过多插一句 自Niloy J Mitra教授的Global contrast based salient region detection出现 最优分割到底鹿死
  • 用 Java 实现的八种常用排序算法

    八种排序算法可以按照如图分类 前置知识 1 算法稳定性 在一个序列中 能保证两个相等的数 经过排序之后 其在序列的前后位置顺序不变 A1 A2 排序前 A1 在 A2 前面 排序后 A1 还在 A2 前面 2 时间复杂度 时间复杂度是用于衡
  • 手把手教你实现一个向量

    文章目录 什么是向量 向量提供哪些接口 实现 宏定义 定义类 成员变量 构造函数与析构函数 构造函数 析构函数 成员函数 size get r put r e expand insert r e remove lo hi remove r
  • Python 实现列队

    1 列队定义 队列是项的有序结合 其中添加新项的一端称为队尾 移除项的一端称为队首 当一个元素从队尾进入队列时 一直向队首移动 直到它成为下一个需要移除的元素为止 最近添加的元素必须在队尾等待 集合中存活时间最长的元素在队首 这种排序成为
  • JavaScript系列——数组元素左右移动N位算法实现

    引言 在自己刚刚毕业不久的时候 去了一家公司面试 面试官现场考了我这道题 我记忆深刻 当时没有想到思路 毫无疑问被面试官当成菜鸟了 最近刚好在研究数组的各种算法实现 就想到这道题 可以拿来实现一下 纪念自己逝去的青春 需求 假设有这样一个数
  • 数据结构——计算节点个数和二叉树高度(C语言版)

    摘自 数据结构 计算节点个数和二叉树高度 C语言版 作者 正弦定理 发布时间 2020 12 12 23 27 09 网址 https blog csdn net chinesekobe article details 111086664
  • Unique Binary Search Trees -- LeetCode

    原题链接 http oj leetcode com problems unique binary search trees 这道题要求可行的二叉查找树的数量 其实二叉查找树可以任意取根 只要满足中序遍历有序的要求就可以 从处理子问题的角度来
  • 如何防止过拟合和欠拟合

    过拟合和欠拟合是模型训练过程中经常出现的问题 两种情况正好相反 现将两者的定义及如何防止进行简要总结 1 过拟合 1 1 定义 是指模型对于训练数据拟合呈现过当的情况 反映到评估指标上就是模型在训练集上的表现很好 但是在测试集上的表现较差
  • 浮生六记

    浮生六记 目录 浮生六记卷一 闺房记乐 002 浮生六记卷二 闲情记趣 015 浮生六记卷三 坎坷记愁 022 浮生六记卷四 浪游记快 034 浮生六记 2 浮生六记卷一 闺房记乐 余生乾隆癸未冬十一月二十有二日 正值太平盛世 且在 衣冠之
  • 用指针访问一维数组

    文章目录 顺序查找 数组方式实现 指针实现方式 对一位数组元素的访问有三种方式 指针变量的关系运算 引例 数组实现方式 主函数 指针实现方式 主函数 一维数组作为函数的参数 实际应用 顺序查找 要求用指针实现 在整数集合r中顺序查找与给定值
  • 机器学习算法GBDT的面试要点总结-上篇

    1 简介 gbdt全称梯度提升决策树 在传统机器学习算法里面是对真实分布拟合的最好的几种算法之一 在前几年深度学习还没有大行其道之前 gbdt在各种竞赛是大放异彩 原因大概有几个 一是效果确实挺不错 二是即可以用于分类也可以用于回归 三是可
  • 索引优化之Explain 及慢查询日志

    索引 本质是数据结构 简单理解为 排好序的快速查找数据结构 以索引文件的形式存储在磁盘中 目的 提高数据查询的效率 优化查询性能 就像书的目录一样 优势 提高检索效率 降低IO成本 排好序的表 降低CPU的消耗劣势 索引实际也是一张表 该表
  • 用两个栈实现队列

    目录 一 栈的基本结构及其接口 二 我的队列结构定义 三 我的队列创建及其初始化 四 我的队列入队 五 我的队列出队 六 我的队列取队头元素 七 我的队列判空 八 我的队列销毁 一 栈的基本结构及其接口 栈的结构定义 typedef int
  • Leetcode1094. 拼车

    Every day a Leetcode 题目来源 1094 拼车 解法1 差分数组 对于本题 设 a i 表示车行驶到位置 i 时车上的人数 我们需要判断是否所有 a i 都不超过 capacity trips i 相当于把 a 中下标从
  • 【数据结构】单链表的定义和操作

    目录 1 单链表的定义 2 单链表的创建和初始化 3 单链表的插入节点操作 4 单链表的删除节点操作 5 单链表的查找节点操作 6 单链表的更新节点操作 7 完整代码 嗨 我是 Filotimo 很高兴与大家相识 希望我的博客能对你有所帮助

随机推荐

  • 1366 - Incorrect string value: ‘\xE8\xBE\xBD\xE5\xAE\x81...‘ for column ‘province_name‘ at row 1

    修改表的字符集编码 ALTER TABLE TABLE NAME CONVERT TO CHARACTER SET utf8mb4
  • 基于LinkedHashMap实现LRU Cache以及手写LRU

    public class LRUCache
  • FreeLibrary问题

    FreeLibrary问题 Delphi Windows SDK API http www delphi2007 net DelphiAPI html delphi 20061127162652164 html 释放动态库时报C盘下的系统文
  • QT学习之QMainWindow详解

    文章目录 1 菜单栏 2 工具栏 3 状态栏 4 铆接部件 5 核心部件 中心部件 6 资源文件 有关QT的学习我们会采取连载更新 传送门 有C 基础如何直接上手QT 最适合新手的第一个Qt小程序 今天更新内容为QMainWindow相关学
  • C++代理模式:Proxy Pattern

    代理模式 为另一个对象提供一个替身或者占位符以控制对这个对象的访问 这样做的好处是 可以在目标对象实现的基础上 增强额外的功能操作 即扩展目标对象的功能 代理需要做的 控制和管理访问 需要时可以扩展目标对象的功能 被代理的对象可以是远程的对
  • 实时音视频的那些事儿(三)—— 音频编码

    前言 上一篇文章 实时音视频的那些事儿 二 音频采集 中我们讲到了如何在iOS Android Windows平台实现音频采集 今天将介绍如何实现音频的编码 一 iOS 中使用 AudioUnit 实现音频编码的过程 AudioUnit 是
  • java IO、NIO、AIO详解

    目录 概述 一 IO流 同步 阻塞 二 NIO 同步 非阻塞 三 NIO2 异步 非阻塞 正文 回到顶部 概述 在我们学习Java的IO流之前 我们都要了解几个关键词 同步与异步 synchronous asynchronous 同步是一种
  • PE文件资源解析(四)光标资源的解析

    光标资源 在这里指的是资源类型为RT CURSOR的资源信息 通过ResHacker看到的效果图如下 解析代码如下 HRSRC hResrc FindResourceEx HMODULE hModule lpType lpName wLan
  • 将数组中的元素拼接为一个字符串

    join 方法 利用JS数组的join 方法即可完成将元素拼接为一个字符串 arrayObject join separator 备注 join 方法不给定分隔符的时候 默认以英文逗号作为分隔符 toString 方法 可以使用JS数组的t
  • 如何破解PDF文件密码(在线破解PDF密码)

    如何破解PDF文件密码 在线破解PDF密码 fcwgw 5d6d com 整理 凌空飞度社区 每当毕业临近的时候 毕业生都会忙着写论文 每逢此时 Adobe Reader就是最忙的了 但是有时候遇到一些加密的PDF文档 Adobe Read
  • Jenkins与git结合使用进行C++代码静态检查

    Jenkins与git结合使用进行C 代码静态检查 在软件开发过程中 静态代码检查是一种常见的工具和实践 可以帮助开发人员在编码阶段尽早发现和解决潜在的问题 本文将介绍如何使用Jenkins和git集成 利用cppcheck进行C 代码的静
  • 建站系列(一)--- 网站基本常识

    目录 相关系列文章 前言 一 因特网 二 网站 三 服务器 四 IP 五 域名 六 DNS 七 Hosts文件 八 端口号 九 URL 十 静态网站 十一 动态网站 相关系列文章 建站系列 一 网站基本常识 建站系列 二 域名 IP地址 U
  • Python 使用requests发送get请求

    get请求是常用的请求之一 相对于post请求简单些 对于传参数的get请求有的还是有难度的 和post请求一样 必须知道每个字段的含义 这样拿到的响应才是正确的 也是我们想要的 不带参数的get请求 import requests hea
  • 自学Android之路---笔记

    1 查看类的源码CTRL b 2 所有的活动即activity必须要在AndroidManifest xml中进行注册才能生效 3 布局多练习
  • 2023华为OD机试真题【缓存需要最少金币数/贪心算法】

    题目描述 静态扫描可以快速识别源代码的缺陷 静态扫描的结果以扫描报告作为输出 1 文件扫描的成本和文件大小相关 如果文件大小为N 则扫描成本为N个金币 2 扫描报告的缓存成本和文件大小无关 每缓存一个报告需要M个金币 3 扫描报告缓存后 后
  • JWT和token的区别

    什么是token token的意思是 令牌 是服务端生成的一串字符串 作为客户端进行请求的一个标识 当用户第一次登录后 服务器生成一个token并将此token返回给客户端 以后客户端只需带上这个token前来请求数据即可 无需再次带上用户
  • Mini-NDN 安装

    1 git clone https github com named data mini ndn 2 install sh 报错1 Traceback most recent call last File usr lib python3 d
  • Spring--IOC容器

    文章目录 Spring IOC容器 一 IOC概念和底层原理 1 官方概念 2 什么是IOC 3 IOC底层原理 4 降低耦合的历史演变 二 IOC接口 Beanfactory 1 IOC思想基于IOC容器完成 IOC容器底层就是对象工厂
  • java判断是否为序列二叉树 - Kaiqisan

    大家好 都吃晚饭了吗 我是Kaiqisan 是一个已经走出社恐的一般生徒 今天还是二叉树诶嘿嘿 首先还是明确一个概念 何为序列二叉树 答 中序遍历之后序列递增的二叉树为序列二叉树 比如这棵树 4 2 7 1 3 5 8 6 它的中序遍历结果
  • 图的深度遍历

    题目描述 请定一个无向图 顶点编号从0到n 1 用深度优先搜索 DFS 遍历并输出 遍历时 先遍历节点编号小的 输入 输入第一行为整数n 0 lt n lt 100 表示数据的组数 对于每组数据 第一行是两个整数k m 0 k 100 0