哪个网站做的游戏好玩,wordpress微信群机器人,郑州的兼职网站建设,济南网站制作定制公司文章目录 题目描述思路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 、欧拉通路、欧拉回路的判定 前导知识 欧拉通路、欧拉回路、欧拉图 无向图#xff1a; ①设G是连通无向图#xff0c;则称… 文章目录 题目描述思路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;
}欢迎大家批评指正
