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

一笔画--PTA

news 来源：原创 2024/5/8 15:07:44

文章目录

题目描述
思路
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;
}