南海专业网站建设公司,网站建设与运营的预算方案模板,wordpress添加邮件发送,wordpress和织梦百度收录一#xff1a;题目#xff1a;
哥尼斯堡是位于普累格河上的一座城市#xff0c;它包含两个岛屿及连接它们的七座桥#xff0c;如下图所示。
可否走过这样的七座桥#xff0c;而且每桥只走过一次#xff1f;瑞士数学家欧拉(Leonhard Euler#xff0c;1707—1783)最终解…一题目
哥尼斯堡是位于普累格河上的一座城市它包含两个岛屿及连接它们的七座桥如下图所示。
可否走过这样的七座桥而且每桥只走过一次瑞士数学家欧拉(Leonhard Euler1707—1783)最终解决了这个问题并由此创立了拓扑学。
这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面可画过图中每条边仅一次且可以回到起点的一条回路。现给定一个无向图问是否存在欧拉回路
输入格式: 输入第一行给出两个正整数分别是节点数N (1≤N≤1000)和边数M随后的M行对应M条边每行给出一对正整数分别是该条边直接连通的两个节点的编号节点从1到N编号。
输出格式: 若欧拉回路存在则输出1否则输出0。
输入样例1:
6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6输出样例1:
1输入样例2:
5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4输出样例2:
0二思路分析
思路 判断欧拉回路 有向图所有的顶点出度入度临接表。 无向图所有顶点都是偶数度临接表。 还有一个前提是 图得是连通的两种判断方法都有解释 知识快递用到DFS遍历 和 并查集 不熟悉的可以点进去看一下哈
DFS知识速递 并查集知识速递
三上码用DFS遍历输出的元素个数来判断图是否连通
/**思路判断欧拉回路有向图所有的顶点出度入度临接表。无向图所有顶点都是偶数度临接表。还有一个前提是 图得是连通的 */#includebits/stdc.h
using namespace std;typedef struct GNode * PtrGraph;
typedef struct GNode{int Nv;int Ne;int Date[1000][1000];
}gnode;int visited[1000] {0};
vectorintv;void createGraph(PtrGraph G){int N,M;cin N M;G-Nv N;G-Ne M;//邻接矩阵初始化 for( int i 1; i G-Nv; i ){for( int j 1; j G-Nv; j ){G-Date[i][j] 0;}}//往邻接矩阵当中进行赋值 如果这两个点相连就赋值 1 for(int i 0; i G-Ne; i ){int a,b;cin a b;G-Date[a][b] 1;G-Date[b][a] 1;//因为是无向图嘛 所以得再来一个 }
}
//来验证建立的邻接矩阵是否正确
void printGraph(PtrGraph G){for( int i 1; i G-Nv; i){for( int j 1; j G-Nv; j)cout G-Date[i][j] ; cout endl;}
} //引入DFS遍历 主要是用与判断遍历顺序的个数是否等于结点数 如果不等于就是不连通
void DFS_Graph(PtrGraph G,int a){int temp a;v.push_back(temp);visited[a] 1;for( int i 1; i G-Nv; i ){if( visited[i] ! 1 G-Date[a][i] 1){DFS_Graph(G,i); } }
} //处理度数问题即该结点有多少分支 就有多少度
int judgenment(PtrGraph G){for( int i 1; i G-Nv; i ){int count 0; //用于统计某个结点的度数 for(int j 1; j G-Nv; j ){if(G-Date[i][j] 1)count;}if( count % 2 ! 0){return 1;} }return 0; } int main(){PtrGraph G (PtrGraph)malloc(sizeof(struct GNode));createGraph(G);
// printGraph(G);DFS_Graph(G,1);//cout v.size();int flag1 judgenment(G);int flag2 v.size();if( flag1 0 flag2 G-Nv ){cout 1;}else{cout 0;}} 四上嘛第二种做法 就是用到并查集来处理 判断图的连通问题
#includebits/stdc.h
using namespace std;typedef struct GNode * PtrGraph;
typedef struct GNode{int Nv;int Ne;int Date[1001][1001];
}gnode;int N,M;
int Father[1001]; void init(){for( int i 1; i N; i )Father[i] i;
} int find( int a ){int ra;while(Father[r]!r)rFather[r]; //找到他的前导结点int ia,j;while(i!r){ //路径压缩算法jFather[i]; //记录x的前导结点Father[i]r; //将i的前导结点设置为r根节点ij;}return r;
}
//合并
void merg( int x,int y){int a find(x);//查询x的根节点 int b find(y);//查询y的根节点if(a ! b )Father[b] a;//如果根节点不一样的话 将索引值b 的根节点设为 a
} //创建图
void createGraph(PtrGraph G){cin N M;G-Nv N;G-Ne M;init();//邻接矩阵初始化 for( int i 1; i G-Nv; i ){for( int j 1; j G-Nv; j ){G-Date[i][j] 0;}}//往邻接矩阵当中进行赋值 如果这两个点相连就赋值 1 for(int i 0; i G-Ne; i ){int a,b;cin a b;merg(a,b);G-Date[a][b] 1;G-Date[b][a] 1;//因为是无向图嘛 所以得再来一个 }
} //处理度数问题即该结点有多少分支 就有多少度
int judgenment(PtrGraph G){for( int i 1; i G-Nv; i ){int count 0; //用于统计某个结点的度数 for(int j 1; j G-Nv; j ){if(G-Date[i][j] 1)count;}if( count % 2 ! 0){return 1;} }return 0; } int main(){int flag1,flag2 0;PtrGraph G (PtrGraph)malloc(sizeof(struct GNode));createGraph(G);//如果是连通的则最后的根节点为 一个值 否则出现其他值即该图不连通 for( int i 1; i N; i ){if( Father[i] i )flag2;}flag1 judgenment(G);if( flag1 0 flag2 1 ){cout 1;}else{cout 0;}} 五总结
今天看Java视频学到了 一个新词 叫 菜牛哈哈哈哈我知道有菜鸟大牛 第一次听说菜牛 哈哈 晚上刷题时看到欧拉回路我根本就不知道是啥自己的离散数学都忘的差不多了那就跟平时做题一样遇到什么不懂就查阅拿到结果来做题。这个题就是一个判断图的连通是否和无向图中每个结点的度数都为偶数即为欧拉回路40分钟就敲完了。下班的早我就上网上看下别人的代码毕竟肯定有比自己更好的码子所以就看到了其他人的做法用到了并查集我一下就有兴趣了因为并查集我就用过一次不是特别的熟练上一次用还是在PTA题目 朋友圈那里所以出于复习的目的我决定改改看了一个码人家用并查集来处理图的联通问题虽然学过一遍并查集而且还做过一道题但还是忘了于是又看了一遍。这就又验证了一句话 重复就是最好的老师边数多了死知识才能活学活用。
加油别放弃啥前敲代码也能成为一种放松方式累了 困了 不喝乐虎了改为敲上一段代码 哈哈哈哈哈哈 加油加油
