[数据结构与算法]5.6--欧拉路径和欧拉回路

能够有欧拉路径的条件：
1、在无向图中，所有边都是连通的
（1）存在欧拉路径的充分必要条件：度数为奇数的点只能有0或2个
（2）存在欧拉回路的充分必要条件：所有点的度数都是偶数
2、对于有向图，所有边都是连通的
（1）存在欧拉路径的充分必要条件：要么所有点的出度均等于入度；要么除了两个点之外，其余所有点的出度等于入度，剩余两个点；一个满足出度比入度多1（起点），另外一个满足入度比出度多1（终点）
（2）存在欧拉回路的充分必要条件：所有点的出度均等于入度。

例题1、AcWing 1124. 骑马修栅栏
无向图的欧拉路径
解题思路：为了满足字典序最小，利用multiset存储，不过要记得删除的时候是删除指针，而不是数，删数会让这个set里面所有的数都删掉。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int N = 510,M = 1e5+10;
int n,m;
int ans[M],top;
int del[M],d[N];
multiset<int> g[N];
void dfs(int u)
{
    while(g[u].size())
    {
        auto it = g[u].begin();
        int t = *it;
        g[u].erase(it);
        g[t].erase(g[t].find(u));
        dfs(t);
    }
    ans[++top] = u;
}
int main()
{
    cin >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int a,b;
        cin >> a >> b;
        g[a].insert(b);
        g[b].insert(a);
        d[a]++,d[b]++;
    }
    int t = 1;
    for (int i = 1; i <= 500; i ++ )
    {
        if(d[i] % 2)
        {
            t = i;
            break;
        }
    }
    dfs(t);
    for(int i=top;i>=1;i--) cout << ans[i] << "\n";
    return 0;
    
}

例题2、送货
有向图的欧拉路径
跟上题一样，不过需要检验，找到起点

// 不存在欧拉路径的条件：不连通或者奇数点的个数不是0或2或者是2但是1号节点的度不是奇数
// 使用并查集来进行判断是否连通
// 因为这里没有重边，用set来记录点的关系。否则可以用multiset

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 10010,M = 1e5+10;
int n,m;
set<int> g[N];
int p[N],ans[M],top;
int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void dfs(int u)
{
    while(g[u].size())
    {
        int t = *g[u].begin();
        g[u].erase(t);
        g[t].erase(u);
        dfs(t);
    }
    top++;
    ans[top] = u;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 1; i <= m; i ++ )
    {
        int a,b;
        cin >> a >> b;
        g[a].insert(b);
        g[b].insert(a);
        p[find(a)] = find(b);
    }
    
    int sum = 0; //奇数点的个数
    for (int i = 1; i <= n; i ++ )
    {
        if(find(1) != find(i))
        {
            // 如果这个点跟一号节点不再一个集合里面，说明不连通
            puts("-1");
            return 0;
        }
        else if(g[i].size() % 2) sum ++;
    }
    
    if(sum != 0 && sum != 2 || sum == 2 && g[1].size() % 2 == 0)
    {
        puts("-1");
        return 0;
    }
    dfs(1);
    for(int i=top;i>=1;i--) cout << ans[i] << " ";
    return 0;
}

例题三、欧拉路径
有向图的欧拉路径

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int N = 1e5+10,M = 2e5+10;
multiset<int> g[M];
int p[M],ans[M],top;
int din[M],dout[M];
int n,m;
int check(vector<int> tmp)
{
    if(tmp.size() == 1 || tmp.size() > 2) return 0;
    if(tmp.size() == 2)
    {
        int v1 = tmp[0],v2 = tmp[1];
        if(dout[v1] - din[v1] == 1 && din[v2] - dout[v2] == 1) return v1;
        else if(dout[v2] - din[v2] == 1 && din[v1] - dout[v1] == 1) return v2;
        else return 0;
    }
    else return 1;
}
void dfs(int u)
{
    while(g[u].size())
    {
        int t = *g[u].begin();
        g[u].erase(g[u].begin());
        dfs(t);
    }
    ans[++top] = u;
    
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int a,b;
        cin >> a >> b;
        g[a].insert(b);
        din[b]++,dout[a]++;
    }
    vector<int> tmp; // 记录出度不等于入度的点
    for (int i = 1; i <= n; i ++ )
    {
        if(din[i] != dout[i])
        {
            tmp.push_back(i);
        }
    }
    
    int t = check(tmp);
    
    if(!t)
    {
        puts("No");
        return 0;
    }
    dfs(t);
    for (int i = top; i >= 1; i -- )
    {
        cout << ans[i] << " ";
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int N = 1e5+10,M = 2e5+10;
vector<int> g[N];
int del[M];
int p[N],ans[M],top;
int din[N],dout[N];
int n,m;
int check(vector<int> tmp)
{
    if(tmp.size() == 1 || tmp.size() > 2) return 0;
    if(tmp.size() == 2)
    {
        int v1 = tmp[0],v2 = tmp[1];
        if(dout[v1] - din[v1] == 1 && din[v2] - dout[v2] == 1) return v1;
        else if(dout[v2] - din[v2] == 1 && din[v1] - dout[v1] == 1) return v2;
        else return 0;
    }
    else return 1;
}
void dfs(int u)
{
    for(int i = del[u];i<g[u].size();i = del[u])
    {
        int t = g[u][i];
        del[u] = i + 1;
        dfs(t);
    }
    ans[++top] = u;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        din[b]++,dout[a]++;
    }
    vector<int> tmp; // 记录出度不等于入度的点
    for (int i = 1; i <= n; i ++ )
    {
        if(din[i] != dout[i])
        {
            tmp.push_back(i);
        }
    }
    
    int t = check(tmp);
    
    if(!t)
    {
        puts("No");
        return 0;
    }
    for (int i = 1; i <= n; i ++ ) sort(g[i].begin(),g[i].end());
    dfs(t);
    for (int i = top; i >= 1; i -- )
    {
        cout << ans[i] << " ";
    }
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖