【洛谷 P1636】Einstein学画画 题解(图论+欧拉通路)

2023-11-26 10:15

本文主要是介绍【洛谷 P1636】Einstein学画画 题解(图论+欧拉通路),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Einstein学画画

题目描述

Einstein 学起了画画。

此人比较懒~~,他希望用最少的笔画画出一张画……

给定一个无向图,包含 n n n 个顶点(编号 1 ∼ n 1 \sim n 1n), m m m 条边,求最少用多少笔可以画出图中所有的边。

输入格式

第一行两个整数 n , m n, m n,m

接下来 m m m 行,每行两个数 a , b a, b a,b a ≠ b a \ne b a=b),表示 a , b a, b a,b 两点之间有一条边相连。

一条边不会被描述多次。

输出格式

一个数,即问题的答案。

样例 #1

样例输入 #1

5 5
2 3
2 4
2 5
3 4
4 5

样例输出 #1

1

提示

对于 50 % 50 \% 50% 的数据, n ≤ 50 n \le 50 n50 m ≤ 100 m \le 100 m100

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1000 1 \le n \le 1000 1n1000 1 ≤ m ≤ 10 5 1 \le m \le {10}^5 1m105


思路

欧拉通路:经过所有顶点且每条边恰好经过一次的通路
欧拉回路:经过所有顶点且每条边恰好经过一次的回路
欧拉图:有欧拉回路的图

根据欧拉图判别定理,无向图G具有欧拉回路当且仅当G是连通的且无奇度顶点。当没有奇度定点时,该图为欧拉图,存在经过所有顶点且每条边恰好经过一次的回路,可以一笔画,直接输出1。

无向图G具有欧拉通路、但没有欧拉回路,当且仅当G是连通的且有2个奇度顶点,其余顶点均为偶度数的,这2个奇度顶点是每条欧拉通路的端点。当奇度定点只有两个时,也可以一笔画。

无向图奇度点的个数一定是偶数个,因为每加一条边,总度数加2。每多两个奇度点,笔画数多1,所以输出 odd / 2


AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e6 + 7;int n, m;
int d[N];
int odd;int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;d[a]++;d[b]++;}odd = 0;for (int i = 1; i <= n; i++) {if (d[i] % 2) {// 奇度顶点odd++;}}if (odd) {cout << odd / 2 << endl;} else {cout << 1 << endl;}return 0;
}

这篇关于【洛谷 P1636】Einstein学画画 题解(图论+欧拉通路)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/425507

相关文章

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

欧拉系统 kernel 升级、降级

系统版本  cat  /etc/os-release  NAME="openEuler"VERSION="22.03 (LTS-SP1)"ID="openEuler"VERSION_ID="22.03"PRETTY_NAME="openEuler 22.03 (LTS-SP1)"ANSI_COLOR="0;31" 系统初始 kernel 版本 5.10.0-136.12.0.

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

nyoj99(并查集+欧拉路+dfs)

单词拼接 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 5 描述 给你一些单词,请你判断能否把它们首尾串起来串成一串。 前一个单词的结尾应该与下一个单词的道字母相同。 如 aloha dog arachnid gopher tiger rat   可以拼接成:aloha.arachnid.dog.gopher.rat.tiger 输入 第一行是一个整

nyoj42(并查集解决欧拉回路)

一笔画问题 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 4 描述 zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来。 规定,所有的边都只能画一次,不能重复画。   输入 第一行只有一个正整数N(N<=10)表示测试数据的组数。 每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<