Conflict Graphs & Bipartite DSU

The Problem That Makes You Rethink "Greedy"

Some greedy problems are applications of graph coloring over constraint networks. The constraint is physical, not abstract.

Given a permutation of \(1..N\), you must sort it using exactly two stacks. Each element from the input goes to either stack 1 or stack 2 (pushed on top). At any point, if the top of either stack equals the next number needed in the output (\(1, 2, 3, \ldots\)), you pop it to the output. The question: can the permutation be sorted this way? If yes, produce a valid assignment. If no, print IMPOSSIBLE.

The Greedy Choice: Don't ask "which stack?" Ask "which elements MUST be in different stacks?" Build a conflict graph, 2-color it with Bipartite DSU.

This problem appears on CSES and is a collision of graph coloring and greedy simulation. Instead of asking "which stack should this element go to?", ask: "which elements are forced into different stacks?"

That reframe changes everything.

Why One Stack Fails: The 231 Pattern

A single stack can sort a permutation if and only if it avoids the 231 pattern. The constraint is physical — consider three elements where their values satisfy \(a[k] < a[i] < a[j]\) with positions \(i < j < k\):

Element \(a[i]\) enters the stack first
Element \(a[j]\) enters next, sitting on top of \(a[i]\)
Element \(a[k]\) is the smallest of the three and needs to come out first
But \(a[j]\) blocks \(a[i]\), and \(a[k]\) hasn't entered yet — deadlock

The stack is LIFO: \(a[j]\) must be popped before \(a[i]\), but the output sequence needs \(a[k]\) first (since \(a[k] < a[i] < a[j]\)). No legal sequence of pops can produce the correct output.

With two stacks, we can separate conflicting elements. The question becomes: which pairs conflict?

Building the Conflict Graph

Two elements \(i\) and \(j\) conflict (cannot share the same stack) when they form a 231-like dependency. The precise rule uses suffix minimums:

Let \(\text{suffixMin}[i]\) = minimum value in \(a[i..n-1]\). Positions \(i\) and \(j\) (with \(i < j\)) conflict if:

\[\text{suffixMin}[j+1] < a[i] \quad \text{and} \quad \text{suffixMin}[j+1] < a[j]\]

In plain language: some future element smaller than both \(a[i]\) and \(a[j]\) will need to be output while both are still in their stack. If they share a stack, the wrong one will be on top.

Conflict graph: nodes are positions, edges connect conflicting pairs that cannot share a stack

Each position is a node. Each conflict is an edge. We need to assign each node one of two colors (stack 1 or stack 2) such that conflicting nodes get different colors. This is exactly graph 2-coloring, which is possible if and only if the conflict graph is bipartite.

If the graph is bipartite, the 2-coloring gives us the stack assignment. If it contains an odd cycle, the answer is IMPOSSIBLE.

2-coloring visualization: bipartite conflict graph with two color classes mapped to stack 1 and stack 2

The Naive Approach: \(O(N^2)\) BFS

The obvious approach: build the conflict graph explicitly and run BFS/DFS to check bipartiteness. But with up to \(N = 200{,}000\) elements, there can be \(O(N^2)\) conflict edges. You build a massive adjacency list, run BFS, and TLE.

The instinct is "I need a faster BFS." The reality is you need a completely different data structure.

For the permutation \([5, 3, 4, 1, 2]\): positions 0 and 1 conflict, 0 and 2 conflict, 1 and 2 conflict, 0 and 3 conflict... The number of conflict pairs can be quadratic. You cannot afford to enumerate them.

The fix: a DSU (Disjoint Set Union) with parity tracking. You don't need to see every edge — you just need to know if forcing two elements into different groups ever creates a contradiction.

Bipartite DSU: \(O(N \log N)\)

DSU with Parity

Each node \(v\) has:

parentNode[v]: the parent in the DSU tree
nodeColor[v]: the distance (mod 2) from \(v\) to its root = the color of \(v\) relative to its root

findRepresentative(v) returns (root, parity_from_root) with path compression. After compression, nodeColor[v] holds the total parity from \(v\) to the root.

uniteWithDifferentColor(u, v) merges two components, forcing \(u\) and \(v\) to have different colors. The golden rule:

\[\text{nodeColor}[\text{rootFirst}] = (1 + \text{parityFirst} + \text{paritySecond}) \bmod 2\]

This ensures \(u\) and \(v\) end up with different parities. We want \(\text{parity}(u) \neq \text{parity}(v)\) after the union. After attaching rootFirst under rootSecond:

parity of \(u\) from rootSecond \(= \text{parityFirst} + \text{nodeColor}[\text{rootFirst}] \pmod{2}\)
parity of \(v\) from rootSecond \(= \text{paritySecond}\)

We need these to differ, so: \(\text{parityFirst} + \text{nodeColor}[\text{rootFirst}] + \text{paritySecond} = 1 \pmod{2}\).

If \(u\) and \(v\) are already in the same component, we just check: do they already have different parities? If not, contradiction — the graph is not bipartite.

Sweepline: Avoiding \(O(N^2)\) Edges

Instead of testing all pairs \((i, j)\), we sweep left to right and maintain an active set of elements still in their stack.

Interval formulation: For each position \(i\), define the interval \([i, \text{exitBoundary}[i]]\) where \(\text{exitBoundary}[i]\) is the position of the element with value \(\text{suffixMin}[i+1]\) — the element must exit before that smaller value arrives.

Why we only union with one active element: We don't need to enumerate every conflict pair. When element \(i\) enters, we union it with the nearest conflicting active element. If element \(i\) conflicts with both \(j_1\) and \(j_2\), and \(j_1\) and \(j_2\) also conflict with each other (their intervals overlap), the DSU transitively propagates the constraint: \(j_1\) and \(j_2\) were already unioned when \(j_2\) entered. So unioning \(i\) with just one of them chains \(i\) into the entire connected component.

Each element enters and leaves the active set exactly once. Each DSU operation is nearly \(O(1)\). Total: \(O(N \log N)\) from the set operations.

Trace: [2, 3, 1, 5, 4]

Trace the full algorithm on the permutation \([2, 3, 1, 5, 4]\) (0-indexed values: \([1, 2, 0, 4, 3]\)).

Step 1: Suffix minimums

Position \(i\)	\(a[i]\)	suffixMin[\(i+1\)]	Meaning
0	1	0	Value 0 appears later, smaller than 1
1	2	0	Value 0 appears later, smaller than 2
2	0	3	Value 3 appears later (from pos 4)
3	4	3	Value 3 appears later, smaller than 4
4	3	5 (sentinel)	Nothing smaller follows

Step 2: Exit bounds and sweepline

Trace the active set carefully:

Position \(i\)	\(a[i]\)	exitBoundary[\(i\)]	Active set before	Union call	Active set after
0	1	\(\text{pos}[0] = 2\)	{}	— (empty)	{(2, 0)}
1	2	\(\text{pos}[0] = 2\)	{(2, 0)}	unite(1, 0) — success	{(2, 0), (2, 1)}
2	0	\(\text{pos}[3] = 4\)	{} (both expired: bound \(2 \leq 2\))	— (empty)	{(4, 2)}
3	4	\(\text{pos}[3] = 4\)	{(4, 2)}	unite(3, 2) — success	{(4, 2), (4, 3)}
4	3	\(n\) (sentinel)	{} (both expired: bound \(4 \leq 4\))	—	{}

No contradiction detected — the graph is bipartite.

Step 3: Read colors from DSU

Position	Value (1-indexed)	findRepresentative parity	Stack
0	2	0	Stack 1
1	3	1	Stack 2
2	1	0	Stack 1
3	5	1	Stack 2
4	4	0	Stack 1

Step 4: Simulate the sorting

Time	Input	Action	Stack 1	Stack 2	Output
1	2	Push 2 to S1	[2]	[]	[]
2	3	Push 3 to S2	[2]	[3]	[]
3	1	Push 1 to S1	[2,1]	[3]	[]
—	—	Pop 1 from S1 (next=1)	[2]	[3]	[1]
—	—	Pop 2 from S1 (next=2)	[]	[3]	[1,2]
—	—	Pop 3 from S2 (next=3)	[]	[]	[1,2,3]
4	5	Push 5 to S2	[]	[5]	[1,2,3]
5	4	Push 4 to S1	[4]	[5]	[1,2,3]
—	—	Pop 4 from S1 (next=4)	[]	[5]	[1,2,3,4]
—	—	Pop 5 from S2 (next=5)	[]	[]	[1,2,3,4,5]

Sorted successfully.

Complete Solution

#include <bits/stdc++.h>
using namespace std;

int parentNode[200010];
int treeRank[200010];
int nodeColor[200010];

pair<int, int> findRepresentative(int element) {
    if (element == parentNode[element]) {
        return {element, 0};
    }
    auto [root, rootParity] = findRepresentative(parentNode[element]);
    parentNode[element] = root;
    nodeColor[element] = (nodeColor[element] + rootParity) % 2;
    return {root, nodeColor[element]};
}

bool uniteWithDifferentColor(int first, int second) {
    auto [rootFirst, parityFirst] = findRepresentative(first);
    auto [rootSecond, paritySecond] = findRepresentative(second);
    if (rootFirst == rootSecond) {
        return (parityFirst != paritySecond);
    }
    if (treeRank[rootFirst] < treeRank[rootSecond]) {
        swap(rootFirst, rootSecond);
        swap(parityFirst, paritySecond);
    }
    parentNode[rootSecond] = rootFirst;
    nodeColor[rootSecond] = (1 + parityFirst + paritySecond) % 2;
    if (treeRank[rootFirst] == treeRank[rootSecond]) {
        treeRank[rootFirst]++;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numElements;
    cin >> numElements;
    vector<int> permutation(numElements);
    for (int i = 0; i < numElements; i++) {
        cin >> permutation[i];
        permutation[i]--;
    }

    iota(parentNode, parentNode + numElements, 0);
    memset(treeRank, 0, sizeof(treeRank));
    memset(nodeColor, 0, sizeof(nodeColor));

    vector<int> suffixMinimum(numElements + 1);
    suffixMinimum[numElements] = numElements;
    for (int i = numElements - 1; i >= 0; i--) {
        suffixMinimum[i] = min(permutation[i], suffixMinimum[i + 1]);
    }

    vector<int> valuePosition(numElements);
    for (int i = 0; i < numElements; i++) {
        valuePosition[permutation[i]] = i;
    }

    vector<int> exitBoundary(numElements);
    for (int i = 0; i < numElements; i++) {
        if (suffixMinimum[i + 1] < numElements) {
            exitBoundary[i] = valuePosition[suffixMinimum[i + 1]];
        } else {
            exitBoundary[i] = numElements;
        }
    }

    set<pair<int, int>> activeSet;
    bool isPossible = true;

    for (int i = 0; i < numElements && isPossible; i++) {
        while (!activeSet.empty() && activeSet.begin()->first <= i) {
            activeSet.erase(activeSet.begin());
        }

        auto conflictIterator = activeSet.lower_bound({i + 1, -1});
        if (conflictIterator != activeSet.end()) {
            if (!uniteWithDifferentColor(i, conflictIterator->second)) {
                isPossible = false;
                break;
            }
        }

        if (exitBoundary[i] > i) {
            activeSet.insert({exitBoundary[i], i});
        }
    }

    if (!isPossible) {
        cout << "IMPOSSIBLE" << "\n";
        return 0;
    }

    vector<int> stackAssignment(numElements);
    for (int i = 0; i < numElements; i++) {
        auto [root, color] = findRepresentative(i);
        stackAssignment[i] = color;
    }

    stack<int> firstStack, secondStack;
    int nextTarget = 0;

    for (int i = 0; i < numElements; i++) {
        if (stackAssignment[i] == 0) {
            firstStack.push(permutation[i]);
        } else {
            secondStack.push(permutation[i]);
        }

        while (true) {
            if (!firstStack.empty() && firstStack.top() == nextTarget) {
                firstStack.pop();
            } else if (!secondStack.empty() && secondStack.top() == nextTarget) {
                secondStack.pop();
            } else {
                break;
            }
            nextTarget++;
        }
    }

    if (nextTarget == numElements) {
        for (int i = 0; i < numElements; i++) {
            cout << (stackAssignment[i] == 0 ? 1 : 2) << (i == numElements - 1 ? "" : " ");
        }
        cout << "\n";
    } else {
        cout << "IMPOSSIBLE" << "\n";
    }

    return 0;
}

Complexity Analysis

Phase	Time	Space
Suffix minimum computation	\(O(N)\)	\(O(N)\)
Sweepline with DSU unions	\(O(N \log N)\)	\(O(N)\)
DSU find with path compression	\(O(\alpha(N))\) per query	—
Simulation (push/pop)	\(O(N)\)	\(O(N)\)
Total	\(O(N \log N)\)	\(O(N)\)

The sweepline ensures we process \(O(N)\) union operations total (each element enters and leaves the active set once). Each DSU operation is nearly \(O(1)\) with path compression and union by rank.

Why This Is a Greedy Algorithm

The conflict graph approach is greedy in a structural sense:

Local decision, global consistency: Each conflict edge is a local constraint (two elements can't share a stack). The DSU greedily propagates these constraints, and bipartiteness gives a globally consistent assignment.
No backtracking: Once we union two elements into different colors, we never undo it. The sweepline processes elements left to right, making irrevocable decisions.
Exchange argument: If a valid 2-coloring exists, any bipartite 2-coloring works (there are only 2 per connected component, and they're symmetric by swapping stacks). So the greedy assignment is as good as any other.

The General Pattern: Constraint Graphs

This technique generalizes beyond two stacks:

2-SAT: When constraints are implications (if X then Y), model as a directed graph and check for consistency with Tarjan's SCC.
Graph coloring: When constraints say "X and Y must differ," bipartiteness gives a 2-coloring. For \(k\) colors, the problem becomes NP-hard in general.
Conflict DSU: Any problem where pairwise "must differ" constraints form a graph, and you need to check if a 2-partition exists.

The key signal: the problem has binary choices (stack 1 or 2, color 0 or 1, team A or B) and pairwise conflict constraints. If you see binary choices with "must-differ" constraints, think bipartite DSU.

Try It

Before looking at the solution above, try this smaller instance by hand:

Input: \([3, 1, 2, 4]\)

Compute the suffix minimums.
Identify which pairs of positions conflict.
Draw the conflict graph. Is it bipartite?
If yes, assign colors and simulate the two-stack sort.

Then try \([2, 4, 1, 3]\). This one should be IMPOSSIBLE — verify that the conflict graph contains an odd cycle. What does the DSU return when it detects the contradiction?

Predict before running: For \([5, 1, 4, 2, 3]\), how many connected components does the conflict graph have? Which positions are forced into the same stack?

Challenge: Modify the problem to three stacks. Why does the conflict graph approach break down? What changes about the coloring requirement? (Hint: 3-coloring is NP-complete.)

Problems

Problem	Link	Difficulty
CSES — Two Stacks Sorting	cses.fi/problemset/task/2402	Hard