对象存储oss做视频网站,深圳网站开发建设服务公司,做民宿需要和多家网站合作吗,wdcp网站建设1.引入
2.概念
3.解决方法
4.例题
5.回顾 1.引入
经典的七桥问题
哥尼斯堡是位于普累格河上的一座城市#xff0c;它包含两个岛屿及连接它们的七座桥#xff0c;如下图所示。 可否走过这样的七座桥#xff0c;而且每桥只走过一次#xff1f;
你怎样证明#xff1f;…1.引入
2.概念
3.解决方法
4.例题
5.回顾 1.引入
经典的七桥问题
哥尼斯堡是位于普累格河上的一座城市它包含两个岛屿及连接它们的七座桥如下图所示。 可否走过这样的七座桥而且每桥只走过一次
你怎样证明
后来大数学家欧拉把它转化成一个几何问题——一笔画问题。 我们的大数学家欧拉找到了它的重要条件
1.奇点的数目不是0个就是2个
奇点就是度为奇数有向图是判断出度与入度是否相等反之为偶点
有向图1、连通 2、所有点出度等于入度或者一个点入度-出度1另外一个点出度-入度1
2.图是联通的
2.概念
欧拉路对于一个图每条边可以且只能访问一次
欧拉回路在欧拉图的情况下最后要回到原点。也就是说欧拉路不一定是欧拉回路但欧拉回路一定是欧拉路 3.解决方法 1.dfs
第一步判断图是否连通
第二步判断奇点个数
很简单但是使用dfs的话就需要很多数组并且用邻接矩阵是最方便的所以费空间
2.并查集
分为G1和G2两个集合G1表示已经联通的G2表示未联通的
利用父亲表示法合并集合效率最高也是上面那两步
4.例题
1 一笔画问题 题目描述 如果一个无向图存在一笔画则一笔画的路径叫做欧拉路如果最后又回到起点那这个路径叫做欧拉回路。 输入 第一行nm0 n 20表示有n个点m条边以下m行描述每条边连接的两点。 输出 如果有欧拉路或欧拉回路输出一条路径即可顶点之间由空格隔开。 如果没有输出NO 样例输入1 5 5 1 2 2 3 3 4 4 5 5 1 样例输出1 1 5 4 3 2 1 解法 1.dfs 简单实用 费空间费时间 2.并查集 效率高快速不费时间不费空间 难费劲 本蒟蒻用的是DFS 1、判断连通性没有判断 就是要判断所有点都是连通的dfs或者并查集 如果不连通输出NO 2、如果连通统计奇点的个数 如果奇点个数为0则为欧拉回路 如果奇点个数为2则为欧拉路 其他情况则输出NO 3、输出一个路径 dfs:
void dfs(int i)
{for(int j1;jn;j){if(g[i][j]1){g[i][j]0;g[j][i]0;dfs(j);}}c[reckon]i;return;
}调题过程很坎坷
40分未判断NO)
#includebits/stdc.h
using namespace std;
#define N 510
int g[N][N],d[N],c[N],n,m,p;
int dfs(int i)
{int j;for(j1;jn;j){if(g[i][j]1){g[i][j]0;g[j][i]0;dfs(j);}}c[p]i;return 0;
}int main()
{cinnm;int x,y;memset(g,0,sizeof(g));for(int i1;im;i){cinxy;g[x][y]1;g[y][x]1;d[x];d[y];}int z1;for(int i1;in;i){if(d[i]%21){zi;}}dfs(z);for(int i1;ip;i){coutc[i] ;}return 0;
}//40分
60分未判断连通性
#includebits/stdc.h
using namespace std;
#define N 510
int g[N][N],d[N],c[N],n,m,reckon,oddity_point;
void dfs(int i)
{for(int j1;jn;j){if(g[i][j]1){g[i][j]0;g[j][i]0;dfs(j);}}c[reckon]i;return;
}int main()
{cinnm;int x,y;memset(g,0,sizeof(g));for(int i1;im;i){cinxy;g[x][y]1;g[y][x]1;d[x];d[y];}int z1;for(int i1;in;i){if(d[i]%21){zi;oddity_point;}}dfs(z);if(oddity_point!2oddity_point!0){coutNO;return 0;}for(int i1;ireckon;i){coutc[i] ;}return 0;
}//60分
100分AC
#includebits/stdc.h
using namespace std;
#define N 510
int g[N][N],d[N],c[N],n,m,reckon,oddity_point,lt;
void dfs(int i)
{for(int j1;jn;j){if(g[i][j]1){g[i][j]0;g[j][i]0;dfs(j);}}c[reckon]i;return;
}int main()
{cinnm;int x,y;memset(g,0,sizeof(g));for(int i1;im;i){cinxy;g[x][y]1;g[y][x]1;d[x];d[y];}int z1;for(int i1;in;i){if(d[i]%21){zi;oddity_point;}if(d[i]0){lt;}}dfs(z);if(oddity_point!2oddity_point!0){coutNO;return 0;}if(lt!0){coutNO;return 0;}for(int i1;ireckon;i){coutc[i] ;}return 0;
}//AC
5.回顾
因为我的测试点没有测出来问题所在
问题 如果1-2-3-4四个点一个环5-6两个点连通奇点个数为2但整个图不连通 我的程序会说YES
可是根本不连通
输出5 6
碰上这样的就必须用DFS并查集了
本蒟蒻偷了个小懒
因为碰上这样的错误输出一定不会是m1个
所以判断一下输出个数是不是不等于m1
如果不等于输出NO。
#includebits/stdc.h
using namespace std;
#define N 510
int g[N][N],d[N],c[N],n,m,reckon,oddity_point,lt;
void dfs(int i)
{for(int j1;jn;j){if(g[i][j]1){g[i][j]0;g[j][i]0;dfs(j);}}c[reckon]i;return;
}
int main()
{cinnm;int x,y;memset(g,0,sizeof(g));for(int i1;im;i){cinxy;g[x][y]1;g[y][x]1;d[x];d[y];}int z1;for(int i1;in;i){if(d[i]%21){zi;oddity_point;}if(d[i]0){lt;}}dfs(z);if(oddity_point!2oddity_point!0){coutNO;return 0;}if(lt!0){coutNO;return 0;}if(reckon!m1){coutNO;return 0;}for(int i1;ireckon;i){coutc[i] ;}return 0;
}
最终我们把无用的代码段删掉调试结束
#includebits/stdc.h
using namespace std;
#define N 510
int g[N][N],d[N],c[N],n,m,reckon,oddity_point,lt;
void dfs(int i)
{for(int j1;jn;j){if(g[i][j]1){g[i][j]0;g[j][i]0;dfs(j);}}c[reckon]i;return;
}
int main()
{cinnm;int x,y;memset(g,0,sizeof(g));for(int i1;im;i){cinxy;g[x][y]1;g[y][x]1;d[x];d[y];}int z1;for(int i1;in;i){if(d[i]%21){zi;oddity_point;}}dfs(z);//判断连通性if(reckon!m1){coutNO;return 0;}//判断奇点个数if(oddity_point!2oddity_point!0){coutNO;return 0;}for(int i1;ireckon;i){coutc[i] ;}return 0;
}