Skip to content

Parity Toggle Layers

You're walking through a dungeon. Some doors are open, others locked. Then you step on a pressure plate --- every door flips. Open ones slam shut. Locked ones swing wide. The maze you memorized is now a different maze. Same nodes, different edges.

This is the toggle pattern. The graph has two faces, and switches flip between them. To track which face you're on, you add one bit to your state.

The Setup: AtCoder abc277_e (Crystal Switches)

Even/odd parity layers: each edge toggles between layers

\(N\) vertices, \(M\) edges. Each edge has a flag \(a_i \in \{0, 1\}\). If \(a_i = 0\), the edge only works when switches are in state 0. If \(a_i = 1\), it only works in state 1. You start in state 0.

\(K\) vertices have crystal switches. Stepping on one toggles the global state: all edges swap their active/inactive status.

Find the minimum number of moves from vertex 1 to vertex \(N\). Each move traverses one active edge.

The State Space

At any point, you care about two things:

  1. Where you are --- which vertex.
  2. Which edges are active --- the parity (0 or 1).

State: (vertex, parity). This gives \(2N\) states total.

Building the 2-Layer Graph

Visualize two copies of the graph stacked vertically:

Layer 0:  1 ---a0--- 2 ---a0--- 3         4
          |                     |
Layer 1:  1          2 ---a1--- 3 ---a1--- 4

In layer 0, only edges with \(a = 0\) are active. In layer 1, only edges with \(a = 1\). These are separate subgraphs --- except at switch vertices, where you can jump between layers.

At a switch vertex \(v\): edge from \((v, 0)\) to \((v, 1)\) and back, with cost 0. The switch is free; it just flips the world.

Key insight. The toggle doesn't move you. It changes the world around you. In the layered graph, this is a vertical edge at the same vertex with cost 0.

0-1 BFS on the Layered Graph

Edges within a layer cost 1 (one move). Switch edges between layers cost 0 (no move consumed). This is a textbook 0-1 BFS: use a deque, push cost-0 transitions to the front, cost-1 transitions to the back.

deque<tuple<int,int>> dq;
dist[0][0] = 0;
dq.push_back({0, 0}); // (parity, vertex_0indexed)

while (!dq.empty()) {
    auto [p, u] = dq.front(); dq.pop_front();
    // Traverse active edges (cost 1)
    for (int v : adj[p][u]) {
        if (dist[p][v] == -1) {
            dist[p][v] = dist[p][u] + 1;
            dq.push_back({p, v});
        }
    }
    // Toggle at switch (cost 0)
    if (has_switch[u] && dist[1-p][u] == -1) {
        dist[1-p][u] = dist[p][u];
        dq.push_front({1-p, u});
    }
}

Gotcha. A common mistake is using a regular queue and treating switch transitions as cost 1. This overcounts by 1 for every toggle used and gives WA.

Trace: 5-Vertex Example

Vertices: 1--5. Start = 1, Target = 5. Switch at vertex 3.

Edge Vertices Active in
1 1 -- 2 parity 0
2 2 -- 3 parity 0
3 3 -- 4 parity 1
4 4 -- 5 parity 1
5 1 -- 5 parity 1

In parity 0, we can only traverse edges 1 and 2. In parity 1, edges 3, 4, and 5.

Step Pop (p, u) dist[p][u] Action
1 (0, 1) 0 push (0, 2) dist=1
2 (0, 2) 1 push (0, 3) dist=2
3 (0, 3) 2 switch! push_front (1, 3) dist=2
4 (1, 3) 2 push (1, 4) dist=3
5 (1, 4) 3 push (1, 5) dist=4
6 (1, 5) 4 target!

Answer: 4. Path: 1 -> 2 -> 3 -> [toggle] -> 4 -> 5.

Without the toggle, vertex 5 is unreachable in parity 0. The switch at vertex 3 opens up the parity-1 edges.

Variant: Expensive Toggles (AtCoder abc395_e)

AtCoder abc395_e (Flip Edge) is the same pattern, but flipping costs \(X\) instead of 0. Now 0-1 BFS becomes Dijkstra.

The only structural change: the vertical edge between layers has cost \(X\).

// Toggle costs X
if (d + X < dist[1-p][u]) {
    dist[1-p][u] = d + X;
    pq.push({d + X, 1-p, u});
}

No switches restrict where you can toggle --- you can flip at any vertex, any time. The question becomes: is paying \(X\) to access different edges worth it?

Key insight. When toggles are free, you flip whenever it helps. When toggles cost \(X\), you have a cost-benefit tradeoff. Dijkstra resolves this automatically --- it never needs you to reason about when to flip.

Variant: Alternating Colors (LC 1129)

LC 1129 (Shortest Path with Alternating Colors) is parity without a switch. Edges are colored red or blue. You must alternate colors on consecutive steps.

State: (node, last_color). Two layers again.

// From layer 0 (last = red), can only take blue edges
for (int v : blue_adj[u]) {
    if (dist[1][v] == -1) {
        dist[1][v] = dist[0][u] + 1;
        q.push({1, v});
    }
}
// From layer 1 (last = blue), can only take red edges
for (int v : red_adj[u]) {
    if (dist[0][v] == -1) {
        dist[0][v] = dist[1][u] + 1;
        q.push({0, v});
    }
}

Every edge forces a layer change. There are no within-layer edges. This is a parity constraint, not a controllable toggle --- but the layered graph construction is identical.

Gotcha. In LC 1129, the first move can use either color. Initialize both dist[0][0] = 0 and dist[1][0] = 0, or add a virtual source connected to node 0 in both layers.

The General Toggle Pattern

All three problems share the same skeleton:

  1. Identify the binary state that changes the graph's edges.
  2. Build two layers of the graph, one per state value.
  3. Connect layers at transition points (switches, forced alternation, paid flips).
  4. Run BFS or Dijkstra on the \(2N\)-node expanded graph.

The binary state varies by problem:

Problem Binary state What it controls
Crystal Switches switch parity which edge set is active
Flip Edge flip parity which edge set is active
Alternating Colors last edge color which edges are available next
Day/night cycle time mod 2 which edges are open

When Not To Expand

If the parity is fully determined by BFS depth (e.g., "alternate every step, no choice"), you can track it implicitly via dist % 2. But when different paths reach the same node with different parities, or when toggling is optional, explicit layers are necessary.

The cost of explicit layers is negligible: \(2N\) states, \(2M + K\) edges.

Complexity

  • States: \(2N\).
  • Edges: \(2M + K\) (original edges in each layer, plus switch transitions).
  • 0-1 BFS: \(O(N + M)\).
  • Dijkstra (weighted toggles): \(O((N + M) \log N)\).

Doubling the graph is nearly free.

Exercises

  1. Layer design. A graph has three types of edges: A, B, C. A switch cycles through which type is active (A -> B -> C -> A). How many layers do you need? What's the state?

  2. Reachability. In the crystal switches problem, can you always reach both layers from the start? What conditions would make one layer permanently unreachable?

  3. Answer extraction. Your BFS finishes. dist[0][N] = 7 and dist[1][N] = 5. What's the answer? Does it matter which layer you end in?

Problems

Problem Link Difficulty
AtCoder abc277_e --- Crystal Switches atcoder.jp/contests/abc277/tasks/abc277_e Hard
AtCoder abc395_e --- Flip Edge atcoder.jp/contests/abc395/tasks/abc395_e Hard
LC 1129 --- Shortest Path with Alternating Colors leetcode.com/problems/shortest-path-with-alternating-colors Medium