Euler road / Euler circuit

Aurora road / Introduction to Euler circuit

The path that passes through all edges of the graph exactly once is called Euler path or Euler road .

The circuit that passes through all edges of the graph exactly once is called Euler circuit .

Discrimination

For undirected graphs G,G Eulerian circuit exists in if and only if G All degrees of non 0 Points of are connected and have no odd degrees .

For undirected graphs G,G There is Euler road in if and only if G Central Africa 0 The points of are connected and G There happens to be 0 or 2 Points of odd degrees （0 One indicates the existence of Euler circuit ）.

For digraphs G,G Eulerian circuit exists in if and only if G All degrees of non 0 The points of are strongly connected and the in degree and out degree of each point are the same .

For digraphs G,G There is Euler road in if and only if ：

take G After changing all directed edges to undirected edges ,G All degrees of non 0 The points of are connected ;

At most, the output minus the input of one point is 1;

At most, the input minus the output of one point is 1;

The in degree of all other points is equal to the out degree .

technological process

First, judge whether there is Eulerian graph in the graph （ Check non 0 Connectivity and degree of points of ）

Then use dfs To construct and solve Euler's road

Make P For the final path sequence , Remember that the starting point of the path is x（ If the undirected graph is all points with even degrees, then find any degree that is not 0 The key point is x, Or find 2 Any one of the odd points is x; If all the in degrees of a digraph are equal to the out degrees, choose any one as x, Otherwise, find out that the degree minus the degree is 1 The key point is x）;

dfs(node u)：

Traverse all of u Connect to the outside side u→v, And u→v Have not been visited before ;

Put edge u→v Mark （ If it is an undirected graph v→u Also mark ）;

dfs(v);

Put edge u→v Add to path sequence P in ;

dfs(x) After the end , take P Side reverse output recorded in , That is, the obtained Euler road 、

Time complexity ：$O(n+m)$（ Find a starting point $O(n)$, Find Oula Road $O(m)$）

Directed graph （ Connectivity is guaranteed ）

vector<int> edge[N];
int n, m, l, f[N], ind[N], outd[N], c[M];
inline void dfs(int x)
{
    while (f[x] < outd[x])
    {
        int y = edge[x][f[x]];
        f[x]++;
        dfs(y);
        c[++l] = y;
    }
}
inline void Euler()
{
    int x = 0, y = 0, z = 0; // x: The starting point ,y: Out degree is bigger than in degree 1,z: The point where the out degree is not equal to the in degree 
    for (int i = 1; i <= n; i++)
    {
        if (ind[i] + 1 == outd[i])
            x = i, ++y;
        if (ind[i] != outd[i])
            ++z;
    }
    if (!((y == 1 && z == 2) || !z))
    {
        printf("No\n");
        return;
    }
    if (!x)
        for (int i = 1; i <= n; i++)
            if (ind[i])
                x = i;
    memset(f, 0, sizeof f);
    l = 0;
    dfs(x);
    c[++l] = x;
    if (l == m + 1)
        printf("Yes\n");
    else
    {
        printf("No\n");
        return;
    }
    for (int i = l; i; --i)
        printf("%d ", c[i]);
}

Undirected graph （ Connectivity is not guaranteed ）

struct Node
{
    int y, idx;
    Node(int _y, int _idx)
    {
        y = _y;
        idx = _idx;
    }
};
vector<Node> edge[N];
int n, m, l, cnt = 1, f[N], d[N], c[M];
bool b[2 * M];
inline void dfs(int x)
{
    while (f[x] < d[x])
    {
        int y = edge[x][f[x]].y, idx = edge[x][f[x]].idx;
        if (!b[idx])
        {
            f[x]++;
            b[idx] = b[idx ^ 1] = true;
            dfs(y);
            c[++l] = y;
        }
        else
            f[x]++;
    }
}
inline void Euler()
{
    int x = 0, y = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] & 1)
            x = i, ++y;
    if (y && y != 2)
    {
        printf("No\n");
        return;
    }
    if (!x)
        for (int i = 1; i <= n; i++)
            if (d[i])
                x = i;
    memset(f, 0, sizeof f);
    memset(b, false, sizeof b);
    l = 0;
    dfs(x);
    c[++l] = x;
    if (l != m + 1)
    {
        printf("No\n");
        return;
    }
    printf("Yes\n");
     for (int i = l; i; --i)
        printf("%d ", c[i]);
}