Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 63 ยท Graphs for Contests

SCC and 2-SAT for Contests

Contest Python templates: iterative Tarjan SCC, condensation DAG tricks, edges needed for strong connectivity, and a 2-SAT class with helper clauses.

Directed graphs with cycles are the home of two contest favorites. Strongly connected components (SCCs) collapse every cycle into one node, turning any directed graph into a DAG you can run dynamic programming on. 2-SAT uses the same machinery to decide yes/no puzzles where every rule involves two choices.

This lesson is the toolbox version. You get an iterative Tarjan that cannot hit Python's recursion limit, three standard things to do with the condensation (DP, source and sink counts, the "make it strongly connected" formula), and a 2-SAT class with helper methods (or, implies, xor, equal, force, at-most-one), all tested against brute force. For explanations of why these algorithms work, see Strongly Connected Components and 2-SAT.

An iterative Tarjan template

Recursion depth equals the DFS depth, which can reach 10^5 in a contest graph. Python's default limit is 1000, and raising it risks a crash. The template below uses an explicit stack. Component ids come out in reverse topological order: component 0 is a sink of the condensation, and edges always go from higher ids to lower ids.

Python Iterative Tarjan SCC, checked with reachability

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The long path finishes quickly because there is no recursion. Time is O(V + E).

Condensation tricks

Collapse each component to one node and keep an edge comp[u] -> comp[v] for each original edge between different components. The result is a DAG. Because Tarjan numbers components in reverse topological order, you can process components in increasing id order to run DP from sinks upward, without a separate topological sort.

Trick 1: collect the most coins

Each node holds some coins. You may start anywhere and walk along edges, revisiting nodes freely, but a node's coins count once. Within a strongly connected component you can visit everything, so the answer is the heaviest path in the condensation, where each component weighs the sum of its coins.

Python Most coins on a walk: condensation DP versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute force explores every state (current node, set of visited nodes), which is exponential, so it only works for tiny graphs; the DP is linear.

Trick 2: edges needed to make the graph strongly connected

Count components with in-degree 0 (sources) and components with out-degree 0 (sinks) in the condensation. If there is a single component, the answer is 0. Otherwise the minimum number of edges to add so that the whole graph becomes strongly connected is

TEXT
max(number of sources, number of sinks)
Python Minimum edges to add: formula versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute force adds edges in all possible ways and takes the smallest number that works, a good sanity check for a formula you would not want to trust blindly.

A 2-SAT class with helpers

2-SAT needs only clauses of two literals, but real statements arrive in other shapes. Keep one class whose methods translate the common shapes into clauses. A literal is an integer v for "variable v is true" and ~v (which is -v - 1) for "false", using 0-based variables so that ~0 = -1.

Statement Clauses added
a or b (a or b)
a implies b (not a or b)
a equals b a implies b and b implies a
a xor b (exactly one true) (a or b) and (not a or not b)
force a true (a or a)
at most one of x1..xk prefix variables, O(k) clauses

For at most one, introduce prefix variables p_i = (x_1 or ... or x_i) with the clauses x_i implies p_i, p_i implies p_{i+1} and p_i implies not x_{i+1}. This replaces the k^2 pairwise clauses by 3k.

Python TwoSat class with helpers and an at-most-one check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notes: variables added by at_most_one extend the answer list, so slice sol[:n] for the original ones. Tarjan's smaller component id is the later one in topological order, so the literal with the smaller id is set to true.

Recognizing the problem

Clue Tool
"Can every node reach every other?" one SCC
Directed graph with cycles, DP on paths condensation, DP in increasing component id
"Minimum edges to add so everything is mutually reachable" max(sources, sinks) (0 if already one component)
Each object has two states and rules link pairs of states 2-SAT
"At most one of these k" inside 2-SAT prefix variables, O(k) clauses
Rules involve three or more objects at once not 2-SAT; try other models

Common mistakes: recursive DFS on deep graphs, mixing up component order conventions between Tarjan (reverse topological) and Kosaraju (topological), forgetting both directions of a clause, and forgetting that auxiliary variables must be ignored in the output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In which order does Tarjan's algorithm number the components?

    A component is completed only after everything reachable from it, so sinks get the small ids, and every edge goes from a higher id to a lower id.
  2. 2. A directed graph has 3 source components and 2 sink components in its condensation (more than one component in total). What is the minimum number of edges to add to make it strongly connected?

    The answer is max(sources, sinks) = max(3, 2) = 3.
  3. 3. How do you encode 'exactly one of a and b is true' in 2-SAT?

    The first clause forbids both false and the second forbids both true, leaving exactly one.
  4. 4. Why does at_most_one use prefix variables?

    Pairwise constraints grow quadratically, while prefix variables encode the same rule with about 3k two-literal clauses.

Summary

  • Use an iterative Tarjan; components come out in reverse topological order, so process ids in increasing order for DP on the condensation.
  • The best coin walk is the heaviest path in the condensation; the edges needed to reach strong connectivity are max(sources, sinks) when more than one component exists.
  • A small TwoSat class with add_or, add_implies, add_equal, add_xor, force and prefix-variable at_most_one covers most statements.
  • Test each template against brute force on tiny random cases.

Next: Geometry Toolkit for Contests