做思维导图的网站,网站建设属于网络还是软件,企业网站 cms,wordpress模板与主题的区别哥尼斯堡的“七桥问题” (25分) 哥尼斯堡是位于普累格河上的一座城市#xff0c;它包含两个岛屿及连接它们的七座桥#xff0c;如下图所示。 可否走过这样的七座桥#xff0c;而且每桥只走过一次#xff1f;瑞士数学家欧拉(Leonhard Euler#xff0c;1707—1783)最终解决… 哥尼斯堡的“七桥问题” (25分) 哥尼斯堡是位于普累格河上的一座城市它包含两个岛屿及连接它们的七座桥如下图所示。 可否走过这样的七座桥而且每桥只走过一次瑞士数学家欧拉(Leonhard Euler1707—1783)最终解决了这个问题并由此创立了拓扑学。 这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面可画过图中每条边仅一次且可以回到起点的一条回路。现给定一个无向图问是否存在欧拉回路 输入格式: 输入第一行给出两个正整数分别是节点数NN (1\le N\le 10001≤N≤1000)和边数MM随后的MM行对应MM条边每行给出一对正整数分别是该条边直接连通的两个节点的编号节点从1到NN编号。 输出格式: 若欧拉回路存在则输出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题解:因为要回到原点所以每个点的入度和出度这和一定是偶数。并查集查看两点之间是否有联系没有联系一定无法连通输出0 #include iostream
#includecstdio
#includestring
#includecstring
#includemap
#includeset
#includequeue
#includevector
#includealgorithm
using namespace std;
int n,m;
int k;
int a[1005],team[1005];
int findteam(int k)
{if (team[k]!k) return team[k]findteam(team[k]);else return k;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i) team[i]i;for(int i1;im;i){int x,y;scanf(%d%d,x,y);a[x]; a[y];int fxfindteam(x);int fyfindteam(y);if (fx!fy) team[fy]fx;}bool flag1;for(int i1;in;i)if (a[i]%2!0){flag0;break;}if (flag){int kfindteam(1);for(int i2;in;i)if (k!findteam(i)) {printf(0\n); return 0;}printf(1\n);}else printf(0\n);return 0;
} 转载于:https://www.cnblogs.com/stepping/p/6523955.html
