首页 > 其他分享 >欧拉回路

欧拉回路

时间:2023-06-18 12:13:55浏览次数:39  
标签:度数 int ++ book 回路 欧拉

日常发癫

  好累好累好累好累。。。好烦好烦好烦好烦。。。


 

欧拉回路

前置概念

度数(出度和入度),对于无向图中一点的度数即为与该点相连的边数。

性质

欧拉回路

 

无向图

每个点的度数均为偶数。可以想象,如果存在欧拉回路则通过一条边进入某个点时,必然需要从另一条边出来,即进入该点的边数与从该点出来的边数相等,即与该点相连的边数为偶数(度数为偶数)。若某无向图中存在度数不为偶数的点,则该无向图不存在欧拉回路。

有向图

每点的入度数等于出度数。与无向图相同,每次从一条边进入则需要从另一条边出来,与之不同的是有向图的边是有向的,所以需要入度数等于出度数。若某有向图中存在入度数不等于出度数的点,则该图不存在欧拉回路。

欧拉路径

欧拉路径相当于把一个欧拉回路从某个点剪开,形成一条路径,所以可以允许存在一个点作为起点,一个点作为终点,这两个点的入度数与出度数的差的绝对值可以为一(起点可以少进入一次,终点可以少出来一次)。

有向图

从起点开始,因此起点可以少进入一次,即起点的入度数可以比出度数少一;到终点即结束,因此终点可以少出来一次,即终点的出度数可以比入度数少一。只能存在两个点(或不存在任何一个点)的入度数与出度数的差的绝对值为一(不能超过一),其中一个(入度数小于出度数)作为起点,另一个(出度数小于入度数)作为终点。否则不存在欧拉路径。

无向图

与有向图相同,起点可以少进入一次,终点可以少出来一次,与有向图不同的是无向图中边是双向的,所以度数为奇数的两个点可以作为起点和终点,若度数为奇数的点为0或2则存在欧拉路径,否则不存在。

思想

深度优先搜索的思想,通过遍历图中的边来找到欧拉回路。

1.选择一个起点,遍历该点连接的边,并将该点添加到欧拉回路中。

2.若该顶点还有未访问的边,则选择一条未访问的边,并将选择该边对应的另一个点。

3.遍历该点的边,继续选择未访问的边对应的点。

4.重复步骤2和步骤3,直到访问完所有边。

代码实现

 欧拉回路

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 5;
int book[N][N];
int idn[N], out[N];
vector<int> ans;
void dfs(int x, int n) {
    for (int i = 1; i <= n; i++) {
        //可能存在两个点之间存在多条边
        if (book[x][i] > 0) {
            book[x][i]--;
            //无向图
            book[i][x]--;
            dfs(i, n);
        }
    }
    //存入路径
    ans.push_back(x);
}
signed main() {
    int n, m;
    cin>>n>>m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin>>u>>v;
        book[u][v]++;
        idn[u]++;
        out[v]++;
        //无向图
        book[v][u]++;
        idn[v]++;
        out[u]++;
    }
    for (int i = 1; i <= n; i++) {
        if (idn[i] & 1) {
            cout<<"不存在欧拉回路";
            return 0;
        }
    }
    //这里从点1开始,因为是欧拉回路,所以其实从哪个点开始都可以
    dfs(1, n);
    int len = ans.size();
    for (int i = len - 1; i >= 0; i--) {
        //逆向输出
        cout<<ans[i]<<" ";
    }
    return 0;
}

欧拉路径

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 const int N = 1e3 + 5;
 5 int book[N][N];
 6 int idn[N], out[N];
 7 vector<int> ans;
 8 void dfs(int x, int n) {
 9     for (int i = 1; i <= n; i++) {
10         //可能存在两个点之间存在多条边
11         if (book[x][i] > 0) {
12             book[x][i]--;
13             //无向图
14             book[i][x]--;
15             dfs(i, n);
16         }
17     }
18     //存入路径
19     ans.push_back(x);
20 }
21 signed main() {
22     int n, m;
23     cin>>n>>m;
24     for (int i = 1; i <= m; i++) {
25         int u, v;
26         cin>>u>>v;
27         book[u][v]++;
28         idn[u]++;
29         out[v]++;
30         //无向图
31         book[v][u]++;
32         idn[v]++;
33         out[u]++;
34     }
35     int head = 0;
36     int cnt = 0;
37     //查找度数为奇数点的个数
38     for (int i = 1; i <= n; i++) {
39         if (idn[i] & 1) {
40             cnt++;
41             //一般会要求按字典序输出,所以找到第一个度数为奇数的作为起点
42             if (head == 0)
43                 head = i;
44         }
45     }
46     if (cnt != 0 && cnt != 2) {
47         cout<<"不存在欧拉路径";
48         return 0;
49     }
50     //全为偶数则可以把任何一个点作为起点
51     if (head == 0)
52         head = 1;
53     dfs(head, n);
54     int len = ans.size();
55     for (int i = len - 1; i >= 0; i--) {
56         //逆向输出
57         cout<<ans[i]<<" ";
58     }
59     return 0;
60 }

标签:度数,int,++,book,回路,欧拉
From: https://www.cnblogs.com/tunecoming/p/17488762.html

相关文章

  • Primes on Interval(欧拉筛+二分+滑动窗口)
    【题面】你决定用素数定理来做一个调查.众所周知,素数又被称为质数,其含义就是除了数字一和本身之外不能被其他任何的数字除尽.现在给定一个正整数序列 ,+1,⋯ ,a,a+1,⋯,b (≤)(a≤b),请找出一个最小值 l,使其满足对于任意一个长度为 l 的子串,都包含 k 个质数.......
  • LED开关电源里的PCB回路设计应该怎么做?
    LED开关电源的研发速度在最近几年中有了明显的技术飞跃,新产品更新换代的速度也加快了许多。作为最后一个设计环节,PCB的设计也显得尤为重要,因为一旦在这一环节出现问题,那么很可能会对整个的LED开关电源系统产生较多的电磁干扰,对于电源工作的稳定性和安全性也都会造成不利影响。那么,P......
  • (数论)判断素数(朴素,根号,埃氏筛,欧拉筛线性筛)
    //最基本求一个素数(on),(osqrt(n))#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;for(inti=2;i<n;i++)//o(n)if(n%i==0){cout<<"no";return0;}for(i......
  • [数论]GCD&LCM&欧拉函——推柿子+例题
    GCD&LCM&欧拉函——推柿子一、\(\sum_{i=1}^{n}[\gcd(i,n)=d]\)\(\sum_{i=1}^{n}[\gcd(i,n)=d]\)\(=\sum_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]\)\(=\phi(\frac{n}{d})\)二、\(\sum_{i=1}^{n}\gcd(i,n)\)\(\sum_{i=1}^{n}\gcd(i,......
  • [浅谈] 欧拉函数
    definition\(\varphi(n)\)表示不超过\(n\)且与\(n\)互质的正整数的个数。欧拉函数是一个数论函数(定义域为正整数)和积性函数(对于互质的正整数\(a,b\)满足\(f(a,b)=f(a)f(b)\))积性函数的性质:\(n=\prodp_i^{a_i}(p_i为质数)\)\(f(n)=\prodf(p_i^{a_i})\)。theorem......
  • 如何对16个末端回路的电气因素进行在线监测——智慧用电精灵AESP100
    安科瑞虞佳豪AESP100系列末端多回路智慧用电在线监测装置应用于户内建筑物及类似场所的工业、商业、民用建筑及基础设施等领域低压终端配电网络。此装置配合断路器使用,对用电线路的关键电气因素,如电压、电流、功率、温度、能耗等进行实时监测,具有预警报警、电能计量统计等功能。......
  • 安科瑞AESP100系列末端多回路智慧用电在线监测装置功能介绍
    安科瑞虞佳豪AESP100系列末端多回路智慧用电在线监测装置(以下简称装置)应用于户内建筑物及类似场所的工业、商业、民用建筑及基础设施等领域低压终端配电网络。此装置配合断路器使用,对用电线路的关键电气因素,如电压、电流、功率、温度、能耗等进行实时监测,具有预警报警、电能计量......
  • POJ2154(Pólya定理与欧拉函数优化)
    题目:Color 题意:将正n边形的n个顶点用n种颜色染色,问有多少种方案(答案modp,且可由旋转互相得到的算一种) 先说说Pólya定理设Q是n个对象的一个置换群,用m种颜色涂染这n个对象,一个对象涂任意一种颜色,则在Q作用下不等价的方案数为:   |Q|为置换群中置换的个数,为将置换q表示成不相杂......
  • Bellman-Ford算法——为什么要循环n-1次?图有n个点,又不能有回路,所以最短路径最多n-1边
    单源最短路径给定一个图,和一个源顶点src,找到从src到其它所有所有顶点的最短路径,图中可能含有负权值的边。Dijksra的算法是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用,Bellman-Ford适合这样的图。在网络路由中,该算法会被用作距......
  • 欧拉函数与容斥
    题目:http://acm.hdu.edu.cn/showproblem.php?pid=1695 题意:给定五个数,其中有和,求满足条件的有序对的个数。题目中    明确说在所有的输入中。分析:问题可以转化为和时,的有序对的个数。那么先比较和的    大小,相同的部分可以用欧拉函数的累加计算,没有公共的部分用容斥计算......