精华内容
下载资源
问答
  • UOJ117. 欧拉回路欧拉回路模板题】
    2021-05-21 15:24:19

    题目大意

    就是让你对有向图和无向图分别求欧拉回路

    非常的模板,但是由于UOJ上毒瘤群众太多了

    所以你必须加上一个小优化

    就是每次访问过一个边就把它删掉

    有点像Dinic的当前弧优化的感觉

    注意是在dfs完一个节点把当前的边加入到栈里面

    然后输出的时候为了保证原来的顺序就直接弹栈就好了

    //Author: dream_maker

    #include

    using namespace std;

    //----------------------------------------------

    typedef pair pi;

    typedef long long ll;

    typedef double db;

    #define fi first

    #define se second

    #define fu(a, b, c) for (int a = b; a <= c; ++a)

    #define fd(a, b, c) for (int a = b; a >= c; --a)

    #define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

    const int INF_of_int = 1e9;

    const ll INF_of_ll = 1e18;

    template

    void Read(T &x) {

    bool w = 1;x = 0;

    char c = getchar();

    while (!isdigit(c) && c != '-') c = getchar();

    if (c == '-') w = 0, c = getchar();

    while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

    }

    if (!w) x = -x;

    }

    template

    void Write(T x) {

    if (x < 0) {

    putchar('-');

    x = -x;

    }

    if (x > 9) Write(x / 10);

    putchar(x % 10 + '0');

    }

    //----------------------------------------------

    const int N = 4e5 + 10;

    struct Edge {

    int v, id, nxt;

    } E[N];

    int head[N], tot = 0;

    int fro[N], to[N], n, m;

    void addedge(int u, int v, int id) {

    E[++tot] = (Edge) {v, id, head[u]};

    head[u] = tot;

    }

    namespace Solve1 {

    int du[N], vis[N];

    stack st;

    void dfs(int u) {

    for (int &i = head[u]; i; i = E[i].nxt) {

    int cur = i;

    if (vis[abs(E[cur].id)]) continue;

    vis[abs(E[cur].id)] = 1;

    dfs(E[cur].v);

    st.push(E[cur].id);

    }

    }

    void solve() {

    fu(i, 1, m) ++du[fro[i]], ++du[to[i]];

    fu(i, 1, n) if (du[i] & 1) {

    printf("NO");

    return;

    }

    fu(i, 1, m) {

    addedge(fro[i], to[i], i);

    addedge(to[i], fro[i], -i);

    }

    fd(i, n, 1) {

    if (head[i]) {

    dfs(i);

    break;

    }

    }

    if ((signed) st.size() != m) {

    printf("NO");

    } else {

    printf("YES\n");

    while (st.size()) {

    Write(st.top()), putchar(' ');

    st.pop();

    }

    }

    }

    }

    namespace Solve2 {

    int in[N], out[N], vis[N];

    stack st;

    void dfs(int u) {

    for (int &i = head[u]; i; i = E[i].nxt) {

    int cur = i;

    if (vis[E[cur].id]) continue;

    vis[E[cur].id] = 1;

    dfs(E[cur].v);

    st.push(E[cur].id);

    }

    }

    void solve() {

    fu(i, 1, m) ++out[fro[i]], ++in[to[i]];

    fu(i, 1, n) if (out[i] ^ in[i]) {

    printf("NO");

    return;

    }

    fu(i, 1, m) addedge(fro[i], to[i], i);

    fu(i, 1, n) {

    if (head[i]) {

    dfs(i);

    break;

    }

    }

    if ((signed) st.size() != m) {

    printf("NO");

    } else {

    printf("YES\n");

    while (st.size()) {

    Write(st.top()), putchar(' ');

    st.pop();

    }

    }

    }

    }

    int main() {

    #ifdef dream_maker

    freopen("input.txt", "r", stdin);

    #endif

    int op; Read(op);

    Read(n), Read(m);

    fu(i, 1, m) Read(fro[i]), Read(to[i]);

    if (op == 1) Solve1::solve();

    else Solve2::solve();

    return 0;

    }

    更多相关内容
  • 欧拉回路

    2021-01-07 09:45:36
    欧拉通路 定义 ...图G中若存在欧拉通路且该欧拉通路是回路,那么该回路称为欧拉回路欧拉回路其实是欧拉通路的特殊情况 判断是否存在欧拉回路 无向图 图G连通,所有节点的度数都是偶数,那么无向图G
  • 自己用C写的无向图找欧拉回路的一个例子。主要用于数据结构的学习
  • 欧拉回路matlab代码
  • 欧拉回路(输出路径) - 欧拉回路 - AcWing 1184 给定一张图,请你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。 输入格式 第一行包含一个整数 t,t∈{1,2},如果 t=1,表示所给图为无向图,如果 t...

    欧拉回路(输出路径) - 欧拉回路 - AcWing 1184

    给定一张图,请你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。

    输入格式

    第一行包含一个整数 t,t∈{1,2},如果 t=1,表示所给图为无向图,如果 t=2,表示所给图为有向图。

    第二行包含两个整数 n,m,表示图的结点数和边数。

    接下来 m 行中,第 i 行两个整数 vi,ui,表示第 i 条边(从 1 开始编号)。

    如果 t=1 则表示 vi 到 ui 有一条无向边。
    如果 t=2 则表示 vi 到 ui 有一条有向边。
    图中可能有重边也可能有自环。

    点的编号从 1 到 n。

    输出格式

    如果无法一笔画出欧拉回路,则输出一行:NO。

    否则,输出一行:YES,接下来一行输出 任意一组 合法方案即可。

    如果 t=1,输出 m 个整数 p1,p2,…,pm。令 e=|pi|,那么 e 表示经过的第 i 条边的编号。如果 pi 为正数表示从 ve 走到 ue,否则表示从 ue 走到 ve。
    如果 t=2,输出 m 个整数 p1,p2,…,pm。其中 pi 表示经过的第 i 条边的编号。

    数据范围

    1 ≤ n ≤ 1 0 5 , 0 ≤ m ≤ 2 × 1 0 5 1≤n≤10^5, 0≤m≤2×10^5 1n105,0m2×105

    输入样例1:

    1
    3 3
    1 2
    2 3
    1 3
    

    输出样例1:

    YES
    1 2 -3
    

    输入样例2:

    2
    5 6
    2 3
    2 5
    3 4
    1 2
    4 2
    5 1
    

    输出样例2:

    YES
    4 1 3 5 2 6
    

    分析:

    欧拉路径/回路存在的充要条件:

    1、对于无向图:

    ① 、 欧 拉 路 径 : 度 数 为 奇 数 的 点 只 能 有 0 或 2 个 。 ①、欧拉路径:度数为奇数的点只能有0或2个。 02

    ② 、 欧 拉 回 路 : 度 数 为 奇 数 的 点 只 能 有 0 个 。 ②、欧拉回路:度数为奇数的点只能有0个。 0

    2、对于有向图:

    ① 、 欧 拉 路 径 : 所 有 点 的 出 度 等 于 入 度 , 或 者 , 一 个 点 的 出 度 比 入 度 多 1 ( 起 点 ) , 一 个 点 的 入 度 比 出 度 多 1 ( 终 点 ) , 其 他 点 的 入 度 与 出 度 相 等 。 ①、欧拉路径:所有点的出度等于入度,或者,\\\qquad一个点的出度比入度多1(起点),一个点的入度比出度多1(终点),其他点的入度与出度相等。 1()1()

    ② 、 欧 拉 回 路 : 所 有 点 的 出 度 等 于 入 度 。 ②、欧拉回路:所有点的出度等于入度。

    遍历欧拉回路:

    从 出 度 不 为 0 的 点 开 始 进 入 搜 索 。 从出度不为0的点开始进入搜索。 0

    注 意 , 先 深 搜 到 底 , 再 将 点 加 入 队 列 。 注意,先深搜到底,再将点加入队列。

    最 后 倒 序 输 出 队 列 , 得 到 的 欧 拉 路 径 。 最后倒序输出队列,得到的欧拉路径。

    优化:

    由 于 每 条 边 仅 需 遍 历 一 次 , 为 了 避 免 很 多 自 环 出 现 在 同 一 个 点 上 的 情 况 , 由于每条边仅需遍历一次,为了避免很多自环出现在同一个点上的情况,

    我 们 每 遍 历 一 条 边 就 跳 过 一 条 边 ( 删 除 ) , 体 现 在 将 邻 接 表 表 头 后 移 , 我们每遍历一条边就跳过一条边(删除),体现在将邻接表表头后移, ()

    另 外 , 无 向 图 建 图 时 , 每 组 边 的 编 号 依 次 为 ( 0 , 1 ) 、 ( 2 , 3 ) 、 . . . ( 2 × m − 2 , 2 × m − 1 ) , 另外,无向图建图时,每组边的编号依次为(0,1)、(2,3)、...(2×m-2,2×m-1), (0,1)(2,3)...(2×m2,2×m1)

    为 了 删 除 某 条 边 的 反 向 边 , 可 以 对 该 边 的 编 号 异 或 1 , 如 0 ⨁ 1 = 1 , 2 ⨁ 1 = 3 。 为了删除某条边的反向边,可以对该边的编号异或1,如0\bigoplus1=1,2\bigoplus1=3。 101=121=3

    代码:

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    const int N=100010, M=400010;
    
    int t,n,m;
    int e[M],ne[M],h[N],idx;
    int ans[M/2],cnt;
    int din[N],dout[N];
    bool st[M];
    
    void add(int a,int b)
    {
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }
    
    void dfs(int u)
    {
        for(int &i=h[u];~i;)  //因为要求欧拉回路,我们从一个点进入就能够遍历到所有边,
        {                    //每次都从h[u]所指向的边继续向下搜索,每次都删除一条边
            if(st[i])
            {
                i=ne[i];    //跳过该边(删除)
                continue; 
            }
            
            st[i]=true;
            if(t==1) st[i^1]=true;  //无向边
            
            int id;
            if(t==1) 
            {
                id=i/2+1;
                if(i & 1) id=-id;
            }
            else id=i+1;
            
            int j=e[i];
            i=ne[i];    //先跳过该边(删除),再进入搜索
            dfs(j);
            
            ans[++cnt]=id;  //先搜索再记录答案,因为要一笔画
        }
    }
    
    int main()
    {
        scanf("%d%d%d",&t,&n,&m);
        
        memset(h,-1,sizeof h);
        int a,b;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            if(t==1) add(b,a);
            din[b]++,dout[a]++;
        }
        
        if(t==1)
        {
            for(int i=1;i<=n;i++)
                if(din[i]+dout[i] & 1)
                {
                    puts("NO");
                    return 0;
                }
        }
        else
        {
            for(int i=1;i<=n;i++)
                if(din[i]!=dout[i])
                {
                    puts("NO");
                    return 0;
                }
        }
        
        for(int i=1;i<=n;i++)   //从一个非孤立点进入搜索
            if(h[i]!=-1)
            {
                dfs(i);
                break;
            }
        
        if(cnt<m)
        {
            puts("NO");
            return 0;
        }
    
        puts("YES");
        for(int i=cnt;i;i--) printf("%d ",ans[i]);  //倒序输出
        puts("");
        
        return 0;
    }
    
    展开全文
  • 有向图的欧拉回路

    2013-12-25 13:15:32
    关于算法与图论中有向图的欧拉回路的判断,判断一个有向图是否有欧拉回路
  • 欧拉通路和欧拉回路

    2022-01-15 16:59:17
    欧拉回路: 如果欧拉路径是一条回路,那么称它为欧拉回路 欧拉图 : 含有欧拉回路的图是欧拉图 判断定理(充要条件): 在无向图中 欧拉路径: 图中所有奇度点的数量为0或2 欧拉回路: 图中所有点的度数都为...

    定义:

    欧拉通路: 如果存在一条通路包含此图中所有的边,则该通路成为欧拉通路,也称欧拉路径(一笔画)
    欧拉回路: 如果欧拉路径是一条回路,那么称它为欧拉回路
    欧拉图 : 含有欧拉回路的图是欧拉图

    判断定理(充要条件):

    在无向图中

    欧拉路径: 图中所有奇度点的数量为0或2
    欧拉回路: 图中所有点的度数都为偶数

    在有向图中

    欧拉路径:1. 所有点的入度等于出度                                                                                                            或者 2.在一点出度比入度大1(起点),一点入度比出度大1(终点),其他点的入度均等于出度
    欧拉回路:所有点的入度等于出度

    算法:寻找一条欧拉回路可以使用dfs(顺着dfs一遍,回溯时记录路径)

    优化

     

    例题(AcWing 1184.欧拉回路

    给定一张图,请你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。

    输入格式

    第一行包含一个整数 t,t∈{1,2},如果 t=1,表示所给图为无向图,如果 t=2,表示所给图为有向图。

    第二行包含两个整数 n,mn,m,表示图的结点数和边数。

    接下来 mm 行中,第 ii 行两个整数 vi,uivi,ui,表示第 ii 条边(从 11 开始编号)。

    • 如果 t=1t=1 则表示 vivi 到 uiui 有一条无向边。
    • 如果 t=2t=2 则表示 vivi 到 uiui 有一条有向边。

    图中可能有重边也可能有自环。

    点的编号从 11 到 nn。

    输出格式

    如果无法一笔画出欧拉回路,则输出一行:NO。

    否则,输出一行:YES,接下来一行输出 任意一组 合法方案即可。

    • 如果 t=1,输出 m 个整数 p1,p2,…,pm。令 e=|pi|,那么 e 表示经过的第 i 条边的编号。如果 pi 为正数表示从 ve 走到 ue,否则表示从 ue 走到 ve。
    • 如果 t=2,输出 m 个整数 p1,p2,…,pm。其中 pi 表示经过的第 i 条边的编号。

    数据范围

    1≤n≤100000
    0≤m≤2×100000

    输入样例1:

    1
    3 3
    1 2
    2 3
    1 3
    

    输出样例1:

    YES
    1 2 -3
    

    输入样例2:

    2
    5 6
    2 3
    2 5
    3 4
    1 2
    4 2
    5 1
    

    输出样例2:

    YES
    4 1 3 5 2 6

    CODE

    #include "bits/stdc++.h"
    using namespace std;
    const int N=1e5+20,M=4e5+20;
    int type,n,m;
    int h[N],e[M],ne[M],idx;
    bool used[M];
    int in[N],out[N];
    int ans[N*2],cnt;
    
    void add(int a,int b){
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }
    
    void dfs(int u){
        for(int &i=h[u];~i;){
            if(used[i]){
                i=ne[i];
                continue;
            }
            used[i]= true;
            if(type==1) used[i^1]= true;
            int t;
            if(type==1){
                t=i/2+1;
                if(i&1) t=-t;
            }
            else t=i+1;
            int j=e[i];
            i=ne[i];
            dfs(j);
            ans[cnt++]=t;
        }
    }
    
    int main(){
    //    freopen("123.in","r",stdin);
        scanf("%d%d%d",&type,&n,&m);
        memset(h,-1,sizeof h);
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);
            if(type==1) add(b,a);
            in[b]++,out[a]++;
        }
        if(type==1){
            for(int i=1;i<=n;i++){
                if((in[i]+out[i])&1){
                    puts("NO");
                    return 0;
                }
            }
        }
        else {
            for(int i=1;i<=n;i++){
                if(in[i]!=out[i]){
                    puts("NO");
                    return 0;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(~h[i]){
                dfs(i);
                break;
            }
        }
        if(cnt<m){
            puts("NO");
            return 0;
        }
        puts("YES");
        for(int i=cnt-1;i>=0;i--){
            cout<<ans[i]<<" ";
        }
        return 0;
    }

    展开全文
  • 欧拉回路C++程序 随机输入任意点数,给出图中存在的欧拉回路
  • 这里以构建一个度全部相同的欧拉回路,并输出欧拉回路的路径 1.构建欧拉回路 连通主要是靠树来保证,首先建立一个度为k的完全图,其中会有很多需要主要的地方 (1)首先构造树 =>保证顶点连通 (2)将度的点...
  • 欧拉回路matlab代码临时股东大会和DC-EGM 该存储库包含EGM和DC-EGM算法的Matlab实现,用于解决消耗和节省的动态随机生命周期模型,以及其他离散选择。 使用以下方法可以解决三个模型: 带有随机收益(和信贷约束)...
  • 算法-欧拉回路(HDU-1878)(包含源程序).rar
  • 信息学竞赛系列教程,欧拉回路和欧拉路径的基本性质,一笔画问题的两种不同解法。
  • 欧拉路径与欧拉回路

    2021-11-22 22:24:46
    1. 欧拉路径 2. 欧拉回路

    欧拉路径欧拉回路基于哥尼斯堡的七桥问题,首先先将其转化为图论的模型,可以发现四个节点的度数都是奇数,分别为3,3,3,5,我们需要从一个起点出发对于图中的每一条边只能够走一次(一笔画问题),一笔画需要满足:除了起点和终点之外其余点的度数为偶数,起点有一条边需要走出去,而终点有一条边走进来,其余边都是一进一出,而七桥问题中所有节点的度数都为奇数所以不满足条件,所以无法完成一笔画。

    欧拉回路与欧拉路径对于无向图和有向图都有相关的性质:

    1. 在无向图中,所有边都是连通的

    (1)存在欧拉路径的充分必要条件:度数为奇数的点只能够有0个或者2个,起点只有一个则度数为奇数的点为0个,否则只有两个;欧拉回路:特殊的欧拉路径,起点与终点是同一个点;

    (2)存在欧拉回路的充分必要条件:度数为奇数的点只能够有0个;

    2. 在有向图中,所有边都是连通的

    (1)存在欧拉路径的充分必要条件:要么所有点的出度均等于入度,要么存在一个点的出度比入度多1,另一个满足入度比出度多1,其余点的出度均等于入度;

    之前只是证明了这些结论的必要条件,如何证明充分条件呢?证明充分性通常有一个常用的技巧:只要能够构造出一种方案将欧拉路径构造出来那么就可以证明结论的充分性。

    (2)存在欧拉回路的充分必要条件:所有点的入度均等于出度

    我们以构造无向图中存在两个起点的欧拉路径为例子:首先从度数为奇数的起点出发开始做深度优先遍历,在dfs遍历的过程中其实是遍历从起点到终点的路径,并且在遍历的过程中存在很多环,此时我们需要将路径环融合在一起即可,不管是环与环还是环与路径最终都可以融合成一条完整的路径,也即按照深度优先的遍历最终我们一定可以将路径分为若干个环和一条链,环与环之间只存在一个交点,将所有的环与路径融合到一起就可以构造一条欧拉路径,如果度数为奇数的点只有0个,按照dfs遍历的顺序最终必然是很多的环,将所有的环拼接在一起就可以构造一条欧拉回路,而对于有向图的欧拉路径与欧拉回路的构造也是类似的。

    欧拉路径与欧拉回路的代码其实都比较简短,在dfs的时候第一条路径一定是从起点到终点的路径,因为从当前点进入就一定会存在一条边出来,所以最终一定会走到终点,中间点的度数一定为偶数,中间点可能存在很多环,如何将环融合进来呢?我们只需要在遍历完节点u的邻节点之后将u加入到欧拉路径的序列中即可, 这样最终得到的就是欧拉路径的逆序。这里需要注意几个细节,因为,一般dfs判重都是以点来判重的,标记点是否已经被访问这样可以保证每一个点只能够被搜一次,欧拉路径是用边来判重的,但是用边来判重的时候可能存在很多个自环,时间复杂度非常高,为O(m ^ 2),我们需要对其优化一下,当我们用过一条边之后那么就将其删除掉,这个时候每条边只会被使用一次,时间复杂度为O(n + m)。

    for next in g[u]:
         dfs(...)
    # dfs扩展完u的邻接点之后将u加入到序列中
    展开全文
  • 现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。 一共两个子任务: 这张图是无向图。(50分) 这张图是有向图。(50分) 图中可能有重边也可能有自环。 如果不可以一笔画,输出一行 ...
  • 欧拉回路matlab代码直升飞机 在Simulink中开发的高保真仿真模型,可与不同类型的多轴直升机兼容。 该模型可用于开发Simulink中的控制算法。 仿真模型包括传感器数据输出,可用于生成代码以对自动驾驶系统(例如...
  • 欧拉回路/欧拉路径

    2022-02-25 23:12:07
    如果此路径的起点和终点相同,则称其为一条欧拉回路。 欧拉路径判定(是否存在): 首先要保证连通 有向图欧拉路径:图中恰好存在 111 个点出度比入度多 111(这个点即为起点 SSS),111 个点入度比出度多 111(这...
  • 欧拉回路的基本概念

    2020-04-14 11:19:52
    欧拉回路相关定义: || 如果图G(有向图或者无向图)中有一条通路,该通路上所有边一次且仅有一次行遍所有顶点,那么这条通路称为欧拉通路 || 如果图G中所有边一次且仅有一次行遍所有顶点,称图G有欧拉回路 || 具有...
  • 搜索与图论之欧拉回路与欧拉路径 前置背景 AOV&AOE AOVAOVAOV网,顶点表示活动,弧表示活动间的优先关系的有向图。 即如果a->b,那么a是b的先决条件。 AOEAOEAOE网,边表示活动,是一个带权的有向无环图, ...
  • 欧拉回路:从起点S出发的路径,每条边只走一次,最终回到起点S。(闭环一笔画) 欧拉路径:从起点S出发的路径,每条边只走一次,不必回到起点S。(开环一笔画) 欧拉图:存在欧拉回路的图 半欧拉图:存在欧拉路径...
  • 个人博客 ...蓝桥杯复习知识点汇总 纸上得来终觉浅,绝知此事要躬行。...欧拉回路:若图G中存在这样一条路径, 使得它恰好通过G中每条边一次,则称该路径为欧拉路径(欧拉通路)。若该路径是一个环路, 则称为欧拉(Eul
  • 2、欧拉回路、欧拉图。有欧拉回路的,就做欧拉图?其实,还有欧拉通路的概念,一笔画完一个图的概念。理一理。 欧拉图:就是从起点出发,可以回到起点的图,每条边经过一次。这个图是可以一笔完成的。 欧拉回路:...
  • 如果图G中所有边一次仅且一次行遍所有顶点的回路称作欧拉回路。具有欧拉回路的图称为欧拉图(简称E图)。具有欧拉通路但不具有欧拉回路的图称为半欧拉图。2. 定理及推论欧拉通路和欧拉回路的判定是很简单的,请看下面...
  • 欧拉通路与欧拉回路 之前,写了图系列一二三,现在出四啦!这也意味着,对于图的部分,可以说50%以上常用的内容就已经过了一遍了。欧拉路的部分会稍微难一点,主要是我们要和定义打交道了。至于其他图的理论,我...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,004
精华内容 4,801
关键字:

欧拉回路

友情链接: IDCT.rar