连通图是不是欧拉图

在已经确认是连通图的基础上,检查是不是欧拉图

#include <bits/stdc++.h>

using namespace std;
const int N = 26;
int ind[N];          //入度

/**
 测试数据:

 欧拉图
 4 4
 1 2
 2 3
 3 4
 4 1

 非欧拉图
 4 4
 1 2
 2 3
 3 4
 1 4
 */
struct Edge {       //记录边的终点,边权的结构体
    int to;         //终点
    int value;      //边权
};
int n, m; //表示图中有n个点,m条边
vector<Edge> p[N];  //使用vector的邻接表
int cnt, start;

int main() {
    //利用邻接表建图
    cin >> n >> m;
    //m条边
    for (int i = 1; i <= m; i++) {
        int u, v;                //点u到点v有一条权值为l的边
        cin >> u >> v;
        p[u].push_back({v, 1});
        //维护入度
        ind[v]++;
    }

    //判断是不是欧拉图
    //出度与入度的数字关系
    for (int i = 1; i <= n; i++) {
        //计算每个结点的出度与入度的差
        int k = p[i].size() - ind[i]; //出度不需要单独维护

        //出度与入度差大于1,则肯定不是欧拉图
        if (abs(k) > 1) {
            cout << "No";
            return 0;
        }

        //如果差是1,那么需要检查是不是2个,2个才是一个入口点,一个出口点
        if (abs(k) == 1) {
            //记录个数
            cnt++;
            //如果出度比入度大1,记录下起点是哪个结点
            if (k == 1) start = i;
        }
    }

    //如果不是0也不是2,那么不是欧拉图
    if (cnt != 0 && cnt != 2) {
        cout << "No";
        return 0;
    }

    //欧拉图
    cout << "Yes" << endl;
    if (start) cout << "出发点:" << start << endl;
    else cout << "任意点都可以是出发点!" << endl;
    return 0;
}

连通图是不是欧拉图

上一篇:Script Control 组件Win7 X64平台运行问题及示例


下一篇:nginx的平滑升级