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

欧拉回路

时间:2023-12-26 12:55:19浏览次数:39  
标签:有向图 int 回路 顶点 节点 欧拉

欧拉回路

欧拉通路:

  • 通过图中每条边且只通过一次,并且经过每一顶点的通路

欧拉回路:

  • 通过图中每条边且只通过一次,并且经过每一顶点的回路

有向图的基图

  • 忽略有向图所有边的方向,得到的无向图称为该有向图的基图
    具有欧拉回路的无向图 G 被称为欧拉图

定理

  • 无向图存在欧拉通路的充要条件是:图联通,并且只有两个奇度节点或者无奇度节点
  • 无向图存在欧拉回路的充要条件:不存在奇度节点
  • 有向图存在欧拉通路的充要条件是:基图联通,并且所有的顶点的出度和入度相等,或者除两个顶点外的出度和入度都相等,而这两个顶点中一个顶点的出度比入度大 1 ,一个顶点的出度比入度小 1
  • 有向图存在欧拉回路的充要条件:基图联通,所有的顶点的出入度相同

欧拉路的构造

  • 无向图为例
  • 如果有奇度节点,那么起点就设成这个节点,否则就设成编号最小的节点
  • 然后从起点开始搜索,然后按照一个逆序存到答案中

Code

点击查看代码
#include<bits/stdc++.h>
using namespace std;
int edge[1000][1000];
//为了方便优先访问编号小的节点,这里使用邻接矩阵来存边
//如果使用vector来存图,那还需要对每个节点连接的边进行排序
int ans[1000000];
int degree[1000];//用于储存每个点的度,以求起点
int p=0;
void dfs(int now)
{
    for(int i=1;i<=1000;i++)//顺序寻找可访问的边,优先找编号小的节点
    {
        if(edge[now][i])//若这条边尚未访问过
        {
            edge[now][i]--;//已访问过的边要删去,防止重复访问
            edge[i][now]--;//有向图的话请删去这一行
            dfs(i);
        }
    }
    ans[++p]=now;//将访问的节点储存进答案数组
    //由于递归的特性,这里储存的是逆序过程
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;//边的个数
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        edge[a][b]++;
        edge[b][a]++;//有向图的话删去这行
        degree[a]++,degree[b]++;//两个点的度都+1
    }
    int start=0;
    for(int i=1;i<=1000;i++)
    {
        if(degree[i]%2)//如果找到奇数点
        {
            start=i;//那这个奇数点就作为起点,由于顺序遍历,这个起点编号必定最小
            break;
        }
    }
    if(!start)//如果还没找到奇数点,说明是欧拉回路
    {
        for(int i=1;i<=1000;i++)
            if(degree[i])//寻找最小的有度的点即可
            {
                start=i;
                break;
            }
    }
    dfs(start);//dfs寻找欧拉路
    for(int i=p;i>=1;i--)
        cout<<ans[i];//输出给定的欧拉路
}

标签:有向图,int,回路,顶点,节点,欧拉
From: https://www.cnblogs.com/BadBadBad/p/OuLaHuiLu.html

相关文章

  • Linux openEuler(欧拉系统)无公网实现ssh远程连接(高效运维!)
    欧拉操作系统(openEuler,简称“欧拉”)是面向数字基础设施的操作系统,支持服务器、云计算、边缘openEuler是面向数字基础设施的操作系统,支持服务器、云计算、边缘计算、嵌入式等应用场景,支持多样性计算,致力于提供安全、稳定、易用的操作系统Cpolar是一种安全的内网穿透云服务,......
  • 欧拉定理 & 扩展欧拉定理 笔记
    欧拉函数欧拉函数定义为:\(\varphi(n)\)表示\(1\simn\)中所有与\(n\)互质的数的个数。关于欧拉函数有下面的性质和用途:欧拉函数是积性函数。可以通过这个性质求出他的公式。\(f(p)=p-1\)。很显然,比质数\(p\)小的所有数都与他互质。\(f(p^2)=p\times......
  • P5091 【模版】扩展欧拉定理
    求\(a^b\bmodm,b\le10^{200000}\)。首先引入三种可以通过取模缩小幂指数的方法。费马小定理:当\(a,p\in\mathbb{Z},\spacep\)为质数且\(p\nmida\)时,\(a^{p-1}\equiv1(\bmod\spacep)\),所以有\(a^b\equiva^{b\bmod(p-1)}(\bmod\spacep)\);欧拉定理:当\(a,m\in\m......
  • 欧拉线性筛
    模板#include<bits/stdc++.h>usingnamespacestd;constintN=1e8+10;intp[N];bitset<N>vis;intn;voidola(){ intcnt=0; for(inti=2;i<=N;i++){ if(!vis[i])p[++cnt]=i; for(intj=1;j<=cnt;j++){ if(i*p[j]>N)break; vis[i*p[j]......
  • 亲情的欧拉定理
    欧拉定理指出产量分配净尽定理,指在完全竞争的条件下,假设长期中规模收益不变,则全部产品正好足够分配给各个要素。白话版如果总量不变的前提下产出的产品正好足够分配给各个要素增加了要素每个要素就会减少生产硬件不更新,本质不变化,分配不是无限的亲情人的的爱总量是......
  • 第四讲 数学知识——欧拉函数
    AcWing873.欧拉函数欧拉函数的定义\(1\)~\(N\)中与\(N\)互质的数的个数被称为欧拉函数,记为\(\phi(N)\)。若在算数基本定理中,\(N=p_1^{a_1}p_2^{a_2}...p_{m}^{a_m}\),则:\(\phi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times...\times\frac{p_m-1}{p_m}\)......
  • 埃筛法求欧拉函数
    普通的欧拉函数求解方法为\(O(\log_{}{N})\),可是当遇到下面这题时,阁下又该如何应对呢?给定一个正整数\(n\),求\(1∼n\)中每个数的欧拉函数之和。其中,\(1\leqn\leq10^6\)。很显然,传统方法复杂度为\(O(n\log_{}{n})\),最大可达\(10^9\),明显超时。那么这里,我们提供一种......
  • 欧拉数(Genshining)
    欧拉数记\(\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\)为\(n\)阶排列\(p[1:n]\)中有\(k\)个\(p[i]<p[i+1](i<n)\)的数量。基础公式和欧拉数·行有\(\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=\left\langle\......
  • 欧拉函数
    定义欧拉函数\(\phi(n)\)代表的是\([1,n]\)之间与\(n\)互质的数量。公式\(\phi(n)=n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times(1-\frac{1}{p_3})\times……\times(1-\frac{1}{p_k})\)其中:\(n\)有\(k\)个质因数,而\(p_i\)就是其中的一个......
  • 欧拉函数模板
    #include<bits/stdc++.h>usingnamespacestd;//欧拉函数,质数vector<int>euler_range(intn){vector<int>phi(n+1),prime;vector<bool>is_prime(n+1,true);is_prime[1]=0,phi[1]=1;for(inti=2;i<=n;i......