第八届蓝桥杯真题c语言c组答案,发现环——第八届蓝桥杯C语言B组（国赛）第四题...

原创

标题&＃xff1a;发现环

小明的实验室有N台电脑&＃xff0c;编号1~N。原本这N台电脑之间有N-1条数据链接相连&＃xff0c;恰好构成一个树形网络。在树形网络上&＃xff0c;任意两台

电脑之间有唯一的路径相连。

不过在最近一次维护网络时&＃xff0c;管理员误操作使得某两台电脑之间增加了一条数据链接&＃xff0c;于是网络中出现了环路。环路上的电脑由于两

两之间不再是只有一条路径&＃xff0c;使得这些电脑上的数据传输出现了BUG。

为了恢复正常传输。小明需要找到所有在环路上的电脑&＃xff0c;你能帮助他吗&＃xff1f;

输入

-----

第一行包含一个整数N。

以下N行每行两个整数a和b&＃xff0c;表示a和b之间有一条数据链接相连。

对于30%的数据&＃xff0c;1 <&＃61; N <&＃61; 1000

对于100%的数据, 1 <&＃61; N <&＃61; 100000&＃xff0c; 1 <&＃61; a, b <&＃61; N

输入保证合法。

输出

----

按从小到大的顺序输出在环路上的电脑的编号&＃xff0c;中间由一个空格分隔。

样例输入&＃xff1a;

5

1 2

3 1

2 4

2 5

5 3

样例输出&＃xff1a;

1 2 3 5

资源约定&＃xff1a;

峰值内存消耗 <256M

CPU消耗 <1000ms

请严格按要求输出&＃xff0c;不要画蛇添足地打印类似&＃xff1a;“请您输入...” 的多余内容。

所有代码放在同一个源文件中&＃xff0c;调试通过后&＃xff0c;拷贝提交该源码。

注意: main函数需要返回0

注意: 只使用ANSI C/ANSI C&＃43;&＃43; 标准&＃xff0c;不要调用依赖于编译环境或操作系统的特殊函数。

注意: 所有依赖的函数必须明确地在源文件中 #include &＃xff0c; 不能通过工程设置而省略常用头文件。

提交时&＃xff0c;注意选择所期望的编译器类型。

本人解题思路&＃xff1a;

主要还是要用到 DFS &＃xff1b;目的是在一棵树中&＃xff0c;找到一个环路&＃xff1b;假定选择在环路中的A结点作为环路的起点&＃xff0c;则A结点也可以作为环

路的终点&＃xff0c;由于不知哪个结点在环路中&＃xff0c;要依次枚举结点 1~N&＃xff1b;

假设用户输入的数据为&＃xff1a;

1 2 (0)

1 3 (0)

2 4 (0)

2 5 (0)

5 6 (0)

5 7 (0)

6 7 (0)

第三列的(0/1/-1)数码的意义&＃xff1a;

0 &＃xff1a;此边未遍历

-1&＃xff1a;此边经判断不在环上

1&＃xff1a;此边在环上

在上图中&＃xff0c;5-6-7组成环&＃xff0c;现在从结点1(以结点1为起点和终点)开始遍历每条边(边的遍历顺序与用户输入的边的顺序有关)&＃xff1b;

在遍历过程中只有回到起点时&＃xff0c;遍历结束。

搜索用户输入的N行数据&＃xff0c;找到有数码1的某行(例子中为第1行)&＃xff0c;先将此行第三列的数码置1(代表遍历过)&＃xff0c;再以此行的另

一个结点(例子中为2)为起点&＃xff0c;搜索N行数据中数码位为0的行数据(1代表遍历过)&＃xff0c;停留在第三行&＃xff0c;将第三列数码位置1&＃xff0c;再

以4为起点继续搜索&＃xff0c;此时4为叶子结点&＃xff0c;搜索数据未果&＃xff0c;所以递归回来将 2 4 (1)——> 2 4 (-1)表示此边定不在环中&＃xff1b;此时

再以2为起点继续搜索N行数据&＃xff0c;停留在 2 5 (1)&＃xff1b;再以5为起点继续搜索&＃xff0c;停留在 5 6(1)&＃xff0c;继续搜索停留在 6 7 (1)&＃xff0c;当停

留在 5 7 (1)的时候&＃xff0c;虽然出现了环 5 - 6 - 7&＃xff0c;但是不满足以 1 为终点&＃xff0c;所以搜索失败(再以7为起点搜索未果)&＃xff1b;递归回来&＃xff0c;

5 7 (-1)&＃xff1b; 6 7 (-1)&＃xff1b;5 6 (-1)&＃xff1b;2 5 (-1)&＃xff1b;继续以1为起点搜索......所以当以5为第一个起点搜索时&＃xff0c;才会搜索成功。

#include

#include

int arr[][]&＃61;{}; //分配3列

int N&＃61;;

int flag&＃61;; //flag&＃61;&＃61;1 表示找到起点&＃xff0c;返回

int unaccess&＃61;;

void dfs(int num,int value){

int i&＃61;;

int j&＃61;;

for(i&＃61;;i<&＃61;N-;i&＃43;&＃43;){

if(flag&＃61;&＃61;){

break;

}

for(j&＃61;;j<&＃61;;j&＃43;&＃43;){

//***************

if(i&＃61;&＃61;N- && j&＃61;&＃61; && arr[i][j]!&＃61;num){ //叶子结点

unaccess&＃61;;

break;

}

if(i&＃61;&＃61;N- && j&＃61;&＃61; && arr[i][j]&＃61;&＃61;num){

if(arr[i][]&＃61;&＃61;){ //叶子结点在第N行&＃xff0c;这条边已经遍历过

unaccess&＃61;;

break;

}

}

//***************

if(arr[i][j]&＃61;&＃61;num && arr[i][]&＃61;&＃61;){

arr[i][]&＃61;;

//***************

if(j&＃61;&＃61;){

if(arr[i][]&＃61;&＃61;value){ //判断是不是起点

flag&＃61;;

break;

}

}

else{

if(arr[i][]&＃61;&＃61;value){

flag&＃61;;

break;

}

}

//***************

if(j&＃61;&＃61;){

dfs(arr[i][],value);

if(flag&＃61;&＃61;){

break;

}

if(unaccess&＃61;&＃61;){

arr[i][]&＃61;-;

}

unaccess&＃61;;

}

else{

dfs(arr[i][],value);

if(flag&＃61;&＃61;){

break;

}

if(unaccess&＃61;&＃61;){

arr[i][]&＃61;-;

}

unaccess&＃61;;

}

}

}

}

}

int main(){

scanf("%d",&N);

int i&＃61;;

int j&＃61;;

for(i&＃61;;i<&＃61;N-;i&＃43;&＃43;){

for(j&＃61;;j<&＃61;;j&＃43;&＃43;){

scanf("%d",&arr[i][j]);

}

}

for(i&＃61;;i<&＃61;N-;i&＃43;&＃43;){ //最后一列为0代表此边可以走

arr[i][]&＃61;;

}

int num&＃61;;

for(num&＃61;;num<&＃61;N;num&＃43;&＃43;){ // num代表起点和终点

dfs(num,num);

if(flag&＃61;&＃61;){

break;

}

else{

for(int z&＃61;;z<&＃61;N-;z&＃43;&＃43;){ //以新的起点继续dfs

arr[z][]&＃61;;

}

}

}

int *RT; //此数组用来存放环中结点

RT&＃61;(int *)malloc(sizeof(int)*(N&＃43;));

for(i&＃61;;i<&＃61;N;i&＃43;&＃43;){

RT[i]&＃61;;

}

for(i&＃61;;i<&＃61;N-;i&＃43;&＃43;){

if(arr[i][]&＃61;&＃61;){

RT[arr[i][]]&＃61;;

RT[arr[i][]]&＃61;;

}

}

for(i&＃61;;i<&＃61;N;i&＃43;&＃43;){

if(RT[i]&＃61;&＃61;){

printf("%d ",i);

}

}

free(RT);

return ;

}

有 错误 或 改良方法  欢迎提出。

12:49:48

2018-05-10

希尔伯特曲线——第八届蓝桥杯C语言B组(国赛)第三题

原创 标题:希尔伯特曲线 希尔伯特曲线是以下一系列分形曲线 Hn 的极限.我们可以把 Hn 看作一条覆盖 2^n × 2^n 方格矩阵的曲线,曲线上一共有 2^n × 2^n 个顶点(包括左下角起点和 ...

磁砖样式——第八届蓝桥杯C语言B组(国赛)第二题

原创 标题:磁砖样式 小明家的一面装饰墙原来是 3*10 的小方格.现在手头有一批刚好能盖住2个小方格的长方形瓷砖.瓷砖只有两种颜色:黄色和橙色. 小明想知道,对于这么简陋的原料,可以贴出多少种不同的 ...

2017第八届蓝桥杯C/C++ B组省赛-日期问题

标题:日期问题 小明正在整理一批历史文献.这些历史文献中出现了很多日期.小明知道这些日期都在1960年1月1日至2059年12月31日.令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的 ...

2017年第八届蓝桥杯C/C++B组省赛题目解析

一. 购物单 小明刚刚找到工作,老板人很好,只是老板夫人很爱购物.老板忙的时候经常让小明帮忙到商场代为购物.小明很厌烦,但又不好推辞. 这不,XX大促销又来了!老板夫人开出了长长的购物单,都是有打折优 ...

2017第八届蓝桥杯C/C++ B组省赛-购物单

标题: 购物单 小明刚刚找到工作,老板人很好,只是老板夫人很爱购物.老板忙的时候经常让小明帮忙到商场代为购物.小明很厌烦,但又不好推辞. 这不,XX大促销又来了!老板夫人开出了长长的购物单,都是有打折 ...

2017第八届蓝桥杯C/C++ B组省赛-等差素数列

标题:等差素数列 2,3,5,7,11,13,....是素数序列. 类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列. 上边的数列公差为30,长度为6. 200 ...

第八届蓝桥杯C/C++ B组省赛----分巧克力

分巧克力 问题描述 儿童节那天有K位小朋友到小明家做客.小明拿出了珍藏的巧克力招待小朋友们. 小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形. 为了公平起见,小明需要从这 N 块巧 ...

2016 第七届蓝桥杯 c/c++ B组省赛真题及解题报告

2016 第七届蓝桥杯 c/c&＃43;&＃43; B组省赛真题及解题报告 勘误1:第6题第4个 if最后一个条件粗心写错了,答案应为1580. 条件应为abs(a[3]-a[7])!&＃61;1,宝宝心理苦啊.!感谢zzh ...

2015年第六届蓝桥杯C/C++B组省赛题目解析

一.奖券数目 有些人很迷信数字,比如带“4”的数字,认为和“死”谐音,就觉得不吉利.虽然这些说法纯属无稽之谈,但有时还要迎合大众的需求.某抽奖活动的奖券号码是5位数(10000-99999),要求其中 ...

随机推荐

Visual Studio2015 常用快捷键

项目相关的快捷键 Ctrl &＃43; Shift &＃43; B &＃61; 生成项目 Ctrl &＃43; Alt &＃43; L &＃61; 显示Solution Explorer(解决方案资源管理器) Shift &＃43; Alt&＃43; C &＃61; 添加 ...

mvc action controller area

获取控制器名称: ViewContext.RouteData.Values["controller"].ToString(); 获取Action名称: ViewContext.Ro ...

Spring中映射Mongodb中注解的解释

spring-data-mongodb中的实体映射是通过MongoMappingConverter这个类实现的.它可以通过注释把java类转换为mongodb的文档. 它有以下几种注释: &＃64;Id - ...

oracle 日期问题

共三部分: 第一部分:oracle sql日期比较: http://www.cnblogs.com/sopost/archive/2011/12/03/2275078.html 第二部分:Oracle ...

解决HtmlAgilityPack无法获取form标签子节点的问题

问题描述 今天使用HtmlAgilityPack提取Form表单下的input节点,发现提取的form节点没有子节点,InnerHtml也是为空,起初以为是标签不全导致,后来分析html代码发现不可能 ...

使用Ninject+Moq在单元测试中抽象数据访问层

一.测试方法的业务逻辑时,通常都需要从数据库读取测试数据,但是每次初始化数据库数据都很麻烦,也会影响到其它业务对数据的访问,怎样抽象数据访问层呢?就是用Moq去模拟数据访问的逻辑     二.步骤如下 ...

easyui validatebox 验证集合