Euler Path and Euler Circuit
Shivansh Goel
782
Graph TheoryDepth-First SearchInterview

Here 0 depicts Non Eulerian Graph .
Here 1 depicts SemiEulerian Graph i.e , only Euler path not circuit .
Here 2 depicts Eulerian Graph .

Every non zero vertex is in the connected graph. Euler Path traverse every edge of the graph and exactly once . Euler Circuit traverse every edge of the graph and exactly once && start vertex ==end vertex. If all vertex degree in the graph is even means it is Eulerian Graph that is both path and cicuit. But if exactly two vertex has odd degree it meams it is semi Eulerian has only path.

class Solution {
public:
    int n;
    void dfs(int node, vector<int> adj[], vector<bool>& visited) {
        visited[node] = true;
        for (int i = 0; i < adj[node].size(); i++) {
            if (!visited[adj[node][i]]) {
                dfs(adj[node][i], adj, visited);
            }
        }
    }
    bool isConnected(vector<int> adj[], vector<bool>& visited) {
        int count = 0;
        int notvisited = -1;
        for (int i = 0; i < n; i++) {
            if (adj[i].size() > 0) {
                notvisited = i;
                break;
            }
        }
        dfs(notvisited, adj, visited);
        for (int i = 0; i < n; i++) {
            if (!visited[i] && adj[i].size() > 0) {
                return 0;
            }
        }
        return true;
    }

    int isEulerCircuit(int V, vector<int> adj[]) {
        n = V;
        vector<bool> visited(n, false);
        if (isConnected(adj, visited) == false) {
            return 0;
        } else {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (adj[i].size() % 2 != 0) {
                    count++;
                }
            }
            if (count == 0) {
                return 2;
            } else if (count == 2) {
                return 1;
            }
        }
        return 0;
    }
};
Comments (1)