连通图是不是欧拉图
欧拉 是不是 连通
2023-09-27 14:28:12 时间
在已经确认是连通图的基础上,检查是不是欧拉图
#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;
}
相关文章
- 【Python 百练成钢】Python语言解决素数筛选问题的几种方式【朴素素数筛、埃氏筛、欧拉筛】
- 欧拉图与哈密顿图12:22
- Uva 10129 - Play on Words 单词接龙 欧拉道路应用
- POJ 2337 Catenyms (有向图欧拉路径,求字典序最小的解)
- MIT线性代数1806(27) 复矩阵 傅里叶矩阵变换 欧拉公式
- MATLAB 欧拉法、改进的欧拉法、龙格库塔法
- 873. 欧拉函数
- 【jzoj 3290】【luogu P6085】Foodie / 吃货 JYY(数位DP)(欧拉回路)
- 【ybt金牌导航8-4-8】最小数(数学)(阶)(欧拉函数)
- 【ybt金牌导航8-4-4】【luogu P2155】互质个数 / 沙拉公主的困惑(gcd)(欧拉函数)