m0_57752468 2021-12-27 11:49 采纳率: 75%
浏览 406
已结题

判断图是否存在欧拉回路

所设计的程序能够通过编译,并能够实现从给定10个结点的图G的邻接矩阵A, 判断G是否存在欧拉回路,存在则输出True,否则输出False。
输入格式
首先输入图G的种类,无向图:输入1,有向图:输入2;然后输入图G的邻接矩阵A。
输出格式
输出True表示存在欧拉回路,False表示不存在欧拉回路。

  • 写回答

1条回答 默认 最新

  • 神仙别闹 2021-12-27 12:23
    关注
    #include <iostream>
    #include <vector>
    using namespace std;
    int n;
    void dfs(int start,vector <vector <int> > &juzhen,vector <int> &vis)
    {
        vis[start]=1;
        for(int j=1;j<=n;j++) {
            if(vis[j]==0&&juzhen[start][j]!=0) {//如果节点没有被访问过,并且两点之间存在边
                dfs(j,juzhen,vis);
            }
        }
    }
    int main()
    {
        int m,x,y,num=0;
        cout<<"请输入节点个数:";
        cin>>n;
        cout<<"请输入边的个数:";
        cin>>m;
        vector <vector <int> > juzhen(n+1,vector <int> (n+1,0));
        vector <int> vis(n+1,0);
        for(int i=1;i<=m;i++) {
            cin>>x>>y;
            juzhen[x][y]=juzhen[y][x]=1;
        }
        dfs(1,juzhen,vis);
        for(int i=1;i<=n;i++) {
            if(vis[i]==0) {//说明该图不是连通图,所以直接输出0返回
                cout<<0<<endl;
                return 0;
            }
        }
        for(int i=1;i<=n;i++) {
            num=0;//num用来判断每个节点的度是否为偶数
            for(int j=1;j<=n;j++) {
                if(juzhen[i][j]==1) num++;
            }
            if(num%2!=0) {//不是偶数,就输出0返回
                cout<<0<<endl;
                return 0;
            }
        }
        cout<<1<<endl;
        return 0;
    }
    
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 6月5日
  • 已采纳回答 5月28日
  • 创建了问题 12月27日

悬赏问题

  • ¥15 python使用pulp线性优化时报错
  • ¥15 为什么我的uibot导入py模块出错呀。py文件放在了uibot里对应的python文件夹了,卸了重安也不行
  • ¥15 开源或低价数据中台哪个最好
  • ¥15 arduino编程出现字符串疑似覆盖现象
  • ¥15 我的b站在没有碰到屏幕的情况下偶尔会自动跳出进度条,就像在屏幕上点了一下一样,但我并没有点。而且视频进度并没有变。这可能是什么原因造成的?
  • ¥30 STK matlab python仿真
  • ¥15 关于IMageEnView 图标定位问题
  • ¥20 求解答(matlab)
  • ¥30 ffmpeg库使用过程中遇到的问题
  • ¥15 pyqt5 中python如何通过Qtwebchannel主动发消息给web前端