Eulerian Path

An eulerian path(or Eulerian trail) is a path of edges that visits all the edges in a graph exactly once.

Checking if there is an Eulerian Path

For directed graph

Calculate the in and out degree for each vertices, and an eulerian path exists if and only if the number of vertices with degree 1 is exactly 2 or 0.
You can start dfs to find the path with the node having out degree - in degree = 1, and end on the one having in degree - out degree = 1 in case it exists, else you can start with any node.

For undirected graph

Calculate the degree of each node, and an eulerian path exists if and only if the number of vertices with odd degree is either 0 or 2.
You can start dfs to find the path with node having odd degree, in case it exists, else you can start with any node.

Eulerian Circuit

An eulerian circuit(or Eulerian cycle) is an eulerian path which starts and ends on the same vertex.

Checking if there is an Eulerian Cycle

For directed graph

Calculate the in and out degree for each vertices, and an eulerian cycle exists if and only if the number of in degrees at every node equals the out degrees.
You can start dfs to find the cycle with any node.

For undirected graph

Calculate the degree of each node, and an eulerian path exists if and only if the number of vertices with odd degree is0.
You can start dfs to find the cycle with any node.

Implementation

For directed graph

vector<int> v[N];
vector<int> EulerPath;
int in[N], out[N];
void dfs_EulerPath(int node) {
	while (out[node]) {
		dfs_EulerPath(v[node][--out[node]]);
	}
	EulerPath.push_back(node);
}

bool findEulerianPath(int n) { /* 1: if its possible to find a eulerPath */
	// calculate the in and out degree for each node
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < (int)v[i].size(); j++)
			in[v[i][j]]++, out[i]++;

	// check if its possible to find euler path or not
	bool ok = 1;
	int numStartNode = 0, numEndNode = 0;
	for (int i = 1; i <= n; i++) {
		if (out[i] - in[i] > 1 || in[i] - out[i] > 1) ok = 0;
		else if (out[i] - in[i] == 1) numStartNode++;
		else if (in[i] - out[i] == 1) numEndNode++;
	}
    
	if (ok) 
        ok = ((numEndNode == 0 && numStartNode == 0) || (numEndNode == 1 && numStartNode == 1));
	if (!ok) return false;

	int node = 1;
	for (int i = 1; i <= n; i++)
		if (out[i] - in[i] == 1)
			node = i;

	dfs_EulerPath(node);
	return true;
}

For undirected graph

set<int> v[N];
vector<int> EulerPath;
int out[N];
void dfs_EulerPath(int node) {
    while (out[node]) {
        node child = *v[node].begin();
        v[node].erase(v[node].find(child));
        v[child].erase(v[child].find(node));

        out[node]--;
        out[child]--;

        dfs_EulerPath(child);
    }
    if (!out[node]) EulerPath.push_back(node);
}

bool findEulerianPath() { /* 1: if its possible to find a eulerPath */
    // calculate the degree for each node
    for (int i = 1; i <= n; i++) {
        debug(i, v[i]);
        trav(it, v[i]) {
            out[i]++;
        }
    }

    // check if its possible to find euler path or not
    node node = -1;
    for (int i = 1; i <= n; i++) {
        if (out[i] & 1) return 0;
        else node = i;
    }
    if (node == -1) return 0;

    dfs_EulerPath(node);
    for (int i = 1; i <= n; i++) {
        if ((int)v[i].size()) return 0;
    }

    return true;
}

Note

  • Make sure that all the edges form a connected graph
  • Similar approach of erasing each edge after visiting them(as in undirected graph) can be used for directed graphs as well.

Practice

S.No PLATFORM TASK SOLUTION
1. LeetCode Cracking the Safe Solution
2. CSES Mail Delivery -
3. CSES Teleporters Path -