401. Seven Bridges - Eulerian Path Existence

Given an undirected graph with n vertices (0-indexed) and m edges (the graph may have multiple edges between the same pair of vertices), determine whether an Eulerian path exists - a walk that uses every single edge exactly once (it need not return to its starting vertex). Print 'Yes' or 'No'.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers, an undirected edge (multiple edges between the same pair are possible). Output: Print 'Yes' if an Eulerian path exists, otherwise print 'No'.

1 <= n <= 1000, 1 <= m <= 10^5

MULTIPLE edges between the SAME pair of vertices each count SEPARATELY toward both endpoints' degree - a vertex connected to another by two distinct edges has degree 2 from that pair alone, not degree 1, an easy detail to undercount if not careful.

Check whether a walk exists that uses every edge of a graph exactly once. Brute force: Try every possible ordering of edges to walk, checking if any uses every edge exactly once - this is factorial time, impractical, when Euler's own elegant degree-counting theorem answers the question directly. Optimised: Euler's classical theorem reduces this entire question to simple DEGREE COUNTING - no actual path construction or search is needed at all, just checking the parity (odd/even) of every vertex's degree and connectivity, a beautiful example of pure mathematical characterization replacing algorithmic search.

Try to actually walk the graph by picking a starting vertex and edge, then recursively trying every unused edge from the current vertex as the next step, backtracking whenever a choice leads to a dead end before all m edges are used. This directly answers the question by attempting to construct a qualifying walk, but in the worst case it explores an enormous number of edge orderings before either finding a valid path or exhausting all possibilities. Time: O(m!) worst case Space: O(m)

Instead of blind backtracking, use Hierholzer's algorithm to actually build a trail: repeatedly follow unused edges from the current vertex until stuck, then splice in additional edge-disjoint circuits found from vertices along the current trail that still have unused edges, until every edge has been incorporated. If this process successfully consumes all m edges starting from an appropriate vertex, an Eulerian path exists. This avoids the combinatorial backtracking of brute force and runs in linear time, but it does more work than necessary since it constructs a full explicit path just to answer a yes/no existence question. Time: O(n + m) Space: O(n + m)

Use the classical theorem directly: an undirected graph has an Eulerian path if and only if every vertex with a nonzero degree lies in a single connected component, and the number of vertices with odd degree is either 0 (an Eulerian circuit, which is also a valid path) or exactly 2. Compute every vertex's degree while reading the edges, run one BFS or DFS from any vertex with an edge to confirm all edge-bearing vertices are reachable from it, and count vertices with odd degree. This sidesteps ever constructing an actual path, answering the existence question directly from two simple, well-understood conditions. Time: O(n + m) Space: O(n + m)

1. An Eulerian path exists if and only if every edge lies in ONE connected component (ignoring vertices with no edges), AND the number of ODD-DEGREE vertices is either 0 (an Eulerian CIRCUIT, also a valid path) or exactly 2 (the path's two endpoints). 2. Count each vertex's DEGREE by how many edge endpoints touch it, INCLUDING multiplicity for repeated edges between the same pair. 3. Check both conditions; if either fails, no Eulerian path exists.

Time: O(n + m) - counting degrees and checking connectivity are both linear. Space: O(n), for the degree-counting array and connectivity check.

Test a graph with duplicate edges between the same pair of vertices (each must add to that vertex's degree separately), isolated vertices with no edges (ignored when checking connectivity), and m at the upper bound of 10^5.

Be ready to recount the historical connection explicitly (Euler's original 1736 solution to the Konigsberg bridge puzzle, which literally founded graph theory as a field) - a great piece of context showing this isn't just an arbitrary puzzle but a foundational result.