一笔画--PTA

2024-03-24 06:04
文章标签 pta 笔画

本文主要是介绍一笔画--PTA,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目描述
  • 思路
  • AC代码

题目描述

在这里插入图片描述
在这里插入图片描述

输入样例1
3 2
1 2
2 3
输出样例1
Y输入样例2
4 3
1 2
1 3
1 4
输出样例2
N输入样例3
1 0
输出样例3
Y

思路

dfs 、欧拉通路、欧拉回路的判定

前导知识

欧拉通路欧拉回路欧拉图
无向图:
①设G是连通无向图,则称经过G的每条边一次并且仅一次的路径为欧拉通路
②如果欧拉通路是回路(起点和终点是同一个顶点),则称此回路为欧拉回路
有向图:
①设D是有向图,D的基图连通,则称经过D的每条边一次并且仅一次的有向路径为有向欧拉通路
②如果有向欧拉通路是有向回路,则称此有向回路为有向欧拉回路
总结
欧拉通路就是从点①出发,到点②,(①②不一定相同)经过该连通图所有路径仅一次;
欧拉回路就是点①和点②一定相同

欧拉通路的判定
①无向图:图连通,只有两个顶点是奇数度,其余都是偶数度的
②有向图:图连通,有一个顶点出度大入度1,有一个顶点入度大出度1,其余都是出度=入度

欧拉回路的判定
①无向图:图连通,所有顶点都是偶数度。
②有向图:图连通,所有的顶点出度=入度。

存储结构
1.二维数组g存储图
2.一维数组cnt统计每个点的度数
3.一位数组vis标记每个数组是否被访问过

具体做法
1.使用邻接矩阵构建图,同时统计每个点的度数
2.该图可以一笔画,肯定存在欧拉通路或者欧拉回路,二者都要考虑,根据前面无向图欧拉通路和欧拉回路的判定知,需要首先满足度数条件,否则该图肯定不能一笔画
3.从每个点进行一次dfs,判断图是否可以连通

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int g[N][N]; //存储节点间的关系
bool vis[N]; //标记每个点是否都被访问过
int cnt[N]; //统计每个点的度数
int num; //统计度数为奇数的点的个数
bool flag; //标记是否可以一笔画
int n, m;void dfs(int x)
{for(int i = 1; i <= n; i ++){if(g[x][i] && !vis[i]){vis[i] = true;dfs(i);}}
}
int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < m; i ++){int x, y;scanf("%d%d", &x, &y);g[x][y] = 1;g[y][x] = 1;cnt[x] ++;cnt[y] ++;}for(int i = 1; i <= n; i ++){if(cnt[i] % 2 == 1) num ++;}if(num != 2 && num != 0) printf("N\n"); //不满足存在欧拉通路 或者 欧拉回路的条件else{for(int i = 1; i <= n; i ++){memset(vis, false, sizeof(vis));vis[i] = true; //起点初始化为访问过flag = true; //假设本次从i出发可以一笔画完dfs(i);for(int j = 1; j <= n; j ++){if(!vis[j]){flag = false;break;}}if(flag) break;}if(flag) printf("Y\n");else printf("N\n");}return 0;
}

欢迎大家批评指正!!!

这篇关于一笔画--PTA的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/840655

相关文章

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数,分析每个整数的每一位数字,求出现次数最多的个位数字。例如给定3个整数1234、2345、3456,其中出现最多次数的数字是3和4,均出现了3次。 输入格式: 输入在第1行中给出正整数N(≤1000),在第二行中给出N个不超过整型范围的非负整数,数字间以空格分隔。 输出格式: 在一行中按格式“M: n1 n2 ...”输出,其中M是最大次数,n

pta-2024年秋面向对象程序设计实验一-java

文章申明:作者也为初学者,解答仅供参考,不一定是最优解; 一:7-1 sdut-sel-2 汽车超速罚款(选择结构) 答案: import java.util.Scanner;         public class Main { public static void main(String[] arg){         Scanner sc=new Scanner(System

PTA L1-037 A除以B

L1-037 A除以B(10分) 真的是简单题哈 —— 给定两个绝对值不超过100的整数A和B,要求你按照“A/B=商”的格式输出结果。 输入格式: 输入在第一行给出两个整数A和B(−100≤A,B≤100),数字间以空格分隔。 输出格式: 在一行中输出结果:如果分母是正数,则输出“A/B=商”;如果分母是负数,则要用括号把分母括起来输出;如果分母为零,则输出的商应为Error。输出的商

PTA - C语言接口题集

目录 6-1 计算两个复数之积(结构体函数)6-2 字符定位(返回字符的地址,指针)6-3 求结构体平均成绩(变量名(数组名)用.;指针(带有*)用->)6-4 删除字符串中数字字符6-5 使用函数找出数组中的最大值6-6 在数组中查找指定元素6-7 按等级统计学生成绩6-8 学生成绩比高低6-11 mystrcpy6-12 mystrcat6-13 mystrcmp6-14 求正整数的因子

PTA - C语言接口题集2

目录 6-24 空间两点间的距离6-25 还书有多难6-26 计算两数的和与差6-27 拆分实数的整数与小数部分6-28 使用函数实现字符串部分复制6-29 判断回文字符串6-30 字符串的连接6-31 指定位置输出字符串6-32 利用指针找最大值6-33 求一组数中的最大值、最小值和平均值6-34 使用函数找出数组中的最大值6-35 每个单词的首字母改为大写6-36 输入单词并排序输出6-

PTA - C语言暑假题集5

目录 7-84 求整数序列中出现次数最多的数7-85 统计字符出现次数7-86 古风排版7-87 散步7-88 小鱼的航程7-89 成绩进步7-90 计算长方形的周长和面积7-91 求一元二次方程的根7-92 找相同字符7-93 连续整数相加7-94 数组逆序7-95 第n小的质数7-96 连续非素数的最大长度7-97 螺旋加密7-98 小X数字母7-99 质数7-100 打印星号三角形7-

PTA输出整数各位数字

作者 颜晖 单位 浙大城市学院 本题要求编写程序,对输入的一个整数,从高位开始逐位分割并输出它的各位数字。 输入格式: 输入在一行中给出一个长整型范围内的非负整数。 输出格式: 从高位开始逐位输出该整数的各位数字,每个数字后面有一个空格。 输入样例: 123456 输出样例: 1 2 3 4 5 6  解题思路:输入要求用长整型long int,对于这种分割数字的要求,我

PTA - C语言国庆题集3

目录 7-41 单词翻转7-42 括号匹配7-43 汉诺塔问题(Hanoi)7-44 判断10的倍数7-45 求5个整数中的最小数7-46 求n个数中的最大值7-47 一批数中最大值最小值7-48 计算平方和7-49 毕达哥拉斯三元组7-50 计算一组x和y7-51 筛法求素数7-52 完美的素数7-53 位运算7-54 头插法创建单链表、遍历链表、删除链表7-55 合并有序数组7-57 英

PTA - C语言国庆题集2

目录 7-21 打妖怪7-22 统计连续高温的最大天数7-23 唱歌比赛打分7-24 找最长的字符串7-25 算龙脉7-26 DNA鉴定7-28 T9键盘7-31 单链表的创建,遍历与销毁7-36 有多少位是7?7-37 选择排序7-38 翻转单词顺序7-39 求因子和最大的数(结构体排序)7-40 按因子和排序(结构体排序) 7-21 打妖怪 话说孙大圣保唐僧西天取经,路上遇到

PTA统计一行文本的单词个数

本题目要求编写程序统计一行字符中单词的个数。所谓“单词”是指连续不含空格的字符串,各单词之间用空格分隔,空格数可以是多个。 输入格式: 输入给出一行字符。 输出格式: 在一行中输出单词个数。 输入样例: Let's go to room 209. 输出样例: 5   解题思路:题目中说所谓“单词”是指连续不含空格的字符串,所以这么判------当前字符不是空格,但下一个字符是