Mail Delivery (Eulerian Circuit)

Problem Overview

Learning Goals

After solving this problem, you will be able to:

• Identify when an Eulerian circuit exists in a graph
• Apply degree conditions for Eulerian circuits (all vertices must have even degree)
• Implement Hierholzer’s algorithm to find an Eulerian circuit
• Verify graph connectivity as a prerequisite for Eulerian circuits

Problem Statement

Problem: Given an undirected graph with n nodes and m edges, find a route that starts and ends at node 1 and visits every edge exactly once. This is an Eulerian circuit.

Input:

• Line 1: n (nodes) and m (edges)
• Next m lines: a b (edge between nodes a and b)

Output:

• A route visiting every edge exactly once, or “IMPOSSIBLE”

Constraints:

• 1 <= n <= 10^5
• 1 <= m <= 2 * 10^5

Example

Input:
5 6
1 2
1 3
2 3
2 4
3 4
4 5

Output:
IMPOSSIBLE

Input:
5 6
1 3
1 2
2 3
4 5
4 5
3 4

Output:
1 3 2 1 3 4 5 4 3

Explanation: In the second example, every edge is traversed exactly once, and the path starts and ends at node 1.

Intuition: How to Think About This Problem

Pattern Recognition

Key Question: When can we traverse every edge exactly once and return to the start?

An Eulerian circuit exists if and only if:

1. Every vertex has even degree - When entering a vertex, you must be able to leave
2. The graph is connected - All edges must be reachable from the starting point

Breaking Down the Problem

1. What are we looking for? A path that uses each edge exactly once and forms a cycle
2. What information do we have? The graph structure (nodes and edges)
3. What’s the relationship between input and output? Degree parity determines existence; Hierholzer’s algorithm finds the path

Analogies

Think of this problem like a mail carrier who needs to deliver mail on every street exactly once and return home. If any intersection has an odd number of streets, the carrier gets “stuck” - they can enter but not leave (or vice versa).

Solution 1: Condition Check Only

Idea

Before attempting to find a circuit, verify that one exists by checking the necessary conditions.

Algorithm

1. Build the adjacency list
2. Check if all vertices with edges have even degree
3. Check if the graph is connected (using DFS/BFS)
4. If conditions fail, output “IMPOSSIBLE”

Code

def check_eulerian_possible(n, edges):
  """
  Check if Eulerian circuit is possible.

  Time: O(n + m)
  Space: O(n + m)
  """
  from collections import defaultdict

  graph = defaultdict(list)
  degree = [0] * (n + 1)

  for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)
    degree[a] += 1
    degree[b] += 1

  # Check 1: All vertices must have even degree
  for i in range(1, n + 1):
    if degree[i] % 2 != 0:
      return False

  # Check 2: Graph must be connected (only check vertices with edges)
  start = -1
  for i in range(1, n + 1):
    if degree[i] > 0:
      start = i
      break

  if start == -1:
    return True  # No edges, trivially true

  visited = set()
  stack = [start]
  while stack:
    node = stack.pop()
    if node in visited:
      continue
    visited.add(node)
    for neighbor in graph[node]:
      if neighbor not in visited:
        stack.append(neighbor)

  # All vertices with edges must be visited
  for i in range(1, n + 1):
    if degree[i] > 0 and i not in visited:
      return False

  return True

Complexity

Solution 2: Hierholzer’s Algorithm (Optimal)

Key Insight

The Trick: Start from any vertex, follow edges (removing them as you go), and when stuck, backtrack while building the circuit.

Algorithm

1. Verify Eulerian conditions (even degrees, connectivity)
2. Start at node 1
3. Follow any available edge, marking it as used
4. When stuck (no outgoing edges), add current node to result and backtrack
5. Continue until all edges are used

Dry Run Example

Let’s trace through with a simple graph:

Graph: 1--2--3--1 (triangle)
Edges: (1,2), (2,3), (3,1)

Initial adjacency:
  1: [2, 3]
  2: [1, 3]
  3: [2, 1]

Step 1: Start at node 1
  Stack: [1]
  Path: []

Step 2: From 1, go to 2 (remove edge 1-2)
  Stack: [1, 2]
  Adjacency updates: 1: [3], 2: [3]

Step 3: From 2, go to 3 (remove edge 2-3)
  Stack: [1, 2, 3]
  Adjacency updates: 2: [], 3: [1]

Step 4: From 3, go to 1 (remove edge 3-1)
  Stack: [1, 2, 3, 1]
  Adjacency updates: 3: [], 1: []

Step 5: Node 1 has no edges, add to path
  Path: [1]
  Stack: [1, 2, 3]

Step 6-8: Continue backtracking
  Final Path: [1, 3, 2, 1]

Visual Diagram

Initial Graph:          After finding circuit:
    1                       1
   / \                     / \
  2---3                   2---3

Circuit: 1 -> 2 -> 3 -> 1
         Uses each edge exactly once

Code

def find_eulerian_circuit(n, edges):
  """
  Find Eulerian circuit using Hierholzer's algorithm.

  Time: O(m) - each edge processed once
  Space: O(n + m) - adjacency list and stack
  """
  from collections import defaultdict

  if not edges:
    print(1)
    return

  graph = defaultdict(list)
  degree = [0] * (n + 1)

  for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)
    degree[a] += 1
    degree[b] += 1

  # Check even degree condition
  for i in range(1, n + 1):
    if degree[i] % 2 != 0:
      print("IMPOSSIBLE")
      return

  # Check connectivity
  start = 1
  if degree[1] == 0:
    print("IMPOSSIBLE")
    return

  visited = set()
  stack = [start]
  while stack:
    node = stack.pop()
    if node in visited:
      continue
    visited.add(node)
    for neighbor in graph[node]:
      if neighbor not in visited:
        stack.append(neighbor)

  for i in range(1, n + 1):
    if degree[i] > 0 and i not in visited:
      print("IMPOSSIBLE")
      return

  # Hierholzer's algorithm
  # Use index-based adjacency for efficient edge removal
  adj = defaultdict(list)
  for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

  circuit = []
  stack = [1]

  while stack:
    v = stack[-1]
    if adj[v]:
      u = adj[v].pop()
      # Remove the reverse edge
      adj[u].remove(v)
      stack.append(u)
    else:
      circuit.append(stack.pop())

  # Check if all edges were used
  if len(circuit) != len(edges) + 1:
    print("IMPOSSIBLE")
    return

  print(" ".join(map(str, circuit)))

# Input handling
n, m = map(int, input().split())
edges = []
for _ in range(m):
  a, b = map(int, input().split())
  edges.append((a, b))
find_eulerian_circuit(n, edges)

Complexity

Common Mistakes

Mistake 1: Forgetting Connectivity Check

# WRONG - Only checks degrees
for i in range(1, n + 1):
  if degree[i] % 2 != 0:
    return "IMPOSSIBLE"
return find_circuit()  # May fail on disconnected graph!

Problem: A graph with even degrees but multiple components has no Eulerian circuit. Fix: Always verify connectivity of vertices with edges.

Mistake 2: Not Removing Both Edge Directions

# WRONG - Only removes forward edge
adj[v].remove(u)
# Forgot: adj[u].remove(v)

Problem: Edge gets traversed twice (once in each direction). Fix: Remove the edge from both adjacency lists.

Mistake 3: Ignoring the Starting Node Requirement

# WRONG - Starting from any node
start = next(node for node in range(1, n+1) if degree[node] > 0)

Problem: Problem requires starting from node 1 specifically. Fix: Check that node 1 has edges; start from node 1.

Edge Cases

When to Use This Pattern

Use Hierholzer’s Algorithm When:

• Finding an Eulerian path or circuit (traverse each edge exactly once)
• Graph has proper degree conditions (all even for circuit, 0 or 2 odd for path)
• Need linear time complexity O(n + m)

Don’t Use When:

• Looking for Hamiltonian path/circuit (visit each vertex once) - different problem
• Graph doesn’t meet Eulerian conditions - no solution exists
• Need shortest path - use Dijkstra/BFS instead

Pattern Recognition Checklist:

• “Traverse every edge exactly once” mentioned? -> Eulerian problem
• All degrees even? -> Eulerian circuit exists
• Exactly 2 odd degree vertices? -> Eulerian path exists
• Graph connected (considering only vertices with edges)? -> Required condition

Related Problems

Easier (Do These First)

Similar Difficulty

Harder (Do These After)

Key Takeaways

1. The Core Idea: An Eulerian circuit exists iff all vertices have even degree and the graph is connected
2. Time Optimization: Hierholzer’s algorithm achieves O(n + m) by cleverly backtracking
3. Space Trade-off: We use O(n + m) space for adjacency list and result storage
4. Pattern: Graph theory - Eulerian circuits are fundamentally about edge traversal

Practice Checklist

Before moving on, make sure you can:

• State the two conditions for an Eulerian circuit to exist
• Explain why odd-degree vertices make circuits impossible
• Implement Hierholzer’s algorithm from scratch
• Handle edge cases (no edges, disconnected, node 1 isolated)

Additional Resources

• CP-Algorithms: Eulerian Path
• CSES Mail Delivery - Find Eulerian circuit
• Wikipedia: Eulerian Path