Two-Pointer Graph

A palindrome reads the same forwards and backwards. On a string, you check with two pointers walking inward. On a graph, both pointers traverse edges simultaneously — and their edge labels must match.

---

The Problem

ABC197-F Construct a Palindrome: Undirected graph with character-labeled edges. Find the shortest path from vertex 1 to vertex N whose edge labels form a palindrome. Output -1 if impossible.

The palindrome constraint couples the beginning and end of the path. You can't just run BFS from one side.

---

The Two-Pointer Insight

Place one pointer at vertex 1, another at vertex N. Both walk inward. At each step, both traverse an edge, and the edge labels must match.

💡 Key insight. State = (u, v) where u is where pointer A is, v is where pointer B is. BFS on pairs finds the shortest matching walk.

---

When Do the Pointers Meet?

• Even-length palindrome: u == v (both pointers at same node). Path length = 2 × BFS distance.
• Odd-length palindrome: u and v are neighbors (connected by any edge). Path length = 2 × BFS distance + 1.

---

Trace

Consider a graph: 1—(a)—2—(b)—3—(b)—4—(a)—5.

Step	(u, v)	Dist	Action
Init	(1, 5)	0	Start: pointer A at 1, pointer B at 5
Pop	(1, 5)	0	Edge (1,2,'a') and (5,4,'a') match → push (2,4)
Pop	(2, 4)	1	Edge (2,3,'b') and (4,3,'b') match → push (3,3)
Pop	(3, 3)	2	u == v → even palindrome, length = 4

Path: 1→2→3→4→5, labels: a-b-b-a. Palindrome!

---

The Code

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,char>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v; char c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    auto enc = [&](int u, int v) -> long long {
        return (long long)u * (n + 1) + v;
    };

    queue<pair<int,int>> q;
    unordered_map<long long, int> dist;
    q.push({1, n});
    dist[enc(1, n)] = 0;

    while (!q.empty()) {
        auto [u, v] = q.front(); q.pop();
        int d = dist[enc(u, v)];

        if (u == v) { cout << 2 * d << "\n"; return 0; }

        // Check odd-length: u and v are neighbors
        for (auto [nv, _] : adj[u])
            if (nv == v) { cout << 2 * d + 1 << "\n"; return 0; }

        // Expand: match edge labels from both sides
        for (auto [nu, cu] : adj[u])
            for (auto [nv, cv] : adj[v])
                if (cu == cv && !dist.count(enc(nu, nv))) {
                    dist[enc(nu, nv)] = d + 1;
                    q.push({nu, nv});
                }
    }
    cout << -1 << "\n";
}

---

Complexity

States: O(N²). Per state: O(deg(u) × deg(v)). Total: O(N² × D²). Feasible for N ≤ 2000 with bounded degree.

⚠ Gotcha. Both pointers use the same undirected adjacency list. Pointer B doesn't walk "backwards" — it walks forward from vertex N into the graph.

---

The General Pattern

Two-pointer graph BFS works when: 1. You match constraints from both ends of a path. 2. The constraint is symmetric (palindrome, matching pairs). 3. Path length is the optimization target.

This is "meet in the middle" for constraint satisfaction, not for speed.

---

Exercises

1. If the graph is directed, pointer B must use reversed edges. Why?
2. Can this find the longest palindrome path? What changes?
3. What if you need the actual path, not just its length?

Problems

Problem	Link	Difficulty
ABC197-F Construct a Palindrome	atcoder.jp	Hard