Strongly Connected Components
Authors: Benjamin Qi, Dong Liu, Neo Wang, Rameez Parwez
Subsets of nodes in directed graphs where each node in a subset can reach each other node in the subset.
SCCs
Focus Problem – try your best to solve this problem before continuing!
View Internal SolutionThe definition of a kingdom in this problem is equivalent to the definition of a strongly connected component. We can compute these components using either Kosaraju's or Tarjan's algorithms, both of which are described below.
Kosaraju's Algorithm
Resources | ||||
---|---|---|---|---|
CPH | ||||
Wikipedia |
Solution (Kosaraju's)
C++
#include <bits/stdc++.h>using namespace std;using vi = vector<int>;#define pb push_backconst int mx = 1e5 + 1;// adj_t is the transpose of adjvi adj[mx], adj_t[mx], S;
Java
import java.io.*;import java.util.*;public class Main {static final int N = 100001;static boolean[] vis = new boolean[N + 1];// Adjacency list of neighborstatic List<Integer>[] adj = new ArrayList[N + 1];// adjT is the transpose of adjstatic List<Integer>[] adjT = new ArrayList[N + 1];
Tarjan's Algorithm
Resources | ||||
---|---|---|---|---|
CPC | ||||
CP2 | ||||
Wikipedia |
Solution (Tarjan's)
C++
#include <bits/stdc++.h>using namespace std;/*** Description: Tarjan's, DFS once to generate* strongly connected components in topological order. $a,b$* in same component if both $a\to b$ and $b\to a$ exist.* Uses less memory than Kosaraju b/c doesn't store reverse edges.* Time: O(N+M)* Source: KACTL* https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/SCC.h
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CSES | Easy | Show TagsDP, SCC | |||
POI | Easy | Show TagsDP, SCC | |||
CF | Normal | Show TagsDP, SCC | |||
Old Gold | Normal | Show TagsSCC | |||
CF | Normal | Show TagsSCC | |||
CF | Hard | Show TagsSCC | |||
POI | Hard | Show TagsSCC | |||
Kattis | Hard | Show TagsSCC | |||
CSES | Very Hard | Show TagsSCC |
2-SAT
Resources
Introduction
The 2-Satisfiability (2-SAT) problem is a specific type of Boolean satisfiability problem where each clause in the given formula contains exactly two literals. The task is to determine whether there exists an assignment of truth values to the variables such that the entire formula is satisfied. A literal is either a variable or its negation. The formula is represented in Conjunctive Normal Form (CNF), which means it is a conjunction (AND) of clauses, where each clause is a disjunction (OR) of exactly two literals.
Algorithm
To solve a 2-SAT problem, consider a Boolean formula in Conjunctive Normal Form (CNF) where each clause contains exactly two literals, such as
The algorithm proceeds by constructing an implication graph, a directed graph where each variable and its negation are represented as nodes. For each clause , we add two directed edges: and . These edges reflect the logical implications necessary to satisfy each clause.
Once the implication graph is constructed, the next step is to identify the strongly connected components (SCCs) of the graph. This can be achieved using Kosaraju's or Tarjan's algorithm, both of which run in linear time. An SCC is a maximal subgraph where every node is reachable from every other node within the subgraph, indicating a tight group of variables and implications.
After identifying the SCCs, we check for consistency. Specifically, we need to ensure that no variable and its negation belong to the same SCC. If such a scenario occurs, it indicates a logical contradiction because it implies that must be both true and false simultaneously, rendering the formula unsatisfiable.
If the graph passes the consistency check, we proceed to determine a satisfying assignment for the variables. This is done by processing the SCCs in topologically sorted order. Topological sorting of the SCCs respects the direction of the implications, ensuring that dependencies are correctly managed. Starting from any SCC with no incoming edges, we assign a truth value to one variable in each SCC. Typically, we set variables to true initially and then propagate this assignment through the graph, ensuring that all implications are satisfied. If a variable is already assigned a truth value due to previous propagations, we skip it to avoid conflicts.
For example, in the formula
, the implication graph would have edges and .
After constructing the graph and finding the SCCs, we check for consistency. Assuming no contradictions are found, we then assign truth values based on the topological order of the SCCs.
This approach ensures that the 2-SAT problem can be solved efficiently, in linear time relative to the number of variables and clauses, leveraging the properties of directed graphs and the power of SCCs to manage logical dependencies and implications systematically. This makes the 2-SAT problem a notable example of a problem that is solvable in polynomial time, despite being a specific case of the generally intractable Boolean satisfiability problem.
Implementation
Now, let's implement the entire algorithm for solving the 2-SAT problem using Kosaraju's algorithm. First, we construct the graph of implications and find all strongly connected components (SCCs). Kosaraju's algorithm efficiently identifies SCCs in time complexity. During the second traversal of the graph, Kosaraju's algorithm visits these SCCs in topological order, allowing us to assign a component number to each vertex .
Subsequently, to determine the satisfiability of the 2-SAT problem:
- For each variable , we compare and . If , it indicates that both and belong to same SCCs, implying a contradiction.
- In such cases, we return to indicate that no valid assignment satisfies the 2-SAT problem.
Below is the implementation of the solution for the 2-SAT problem, utilizing the graph of implications and its transpose , where vertices and correspond to variable and its negation respectively.
C++
struct TwoSatSolver {int n_vars;int n_vertices;vector<vector<int>> adj, adj_t;vector<bool> used;vector<int> order, comp;vector<bool> assignment;TwoSatSolver(int _n_vars): n_vars(_n_vars), n_vertices(2 * n_vars), adj(n_vertices),
Focus Problem – try your best to solve this problem before continuing!
It is a straightforward 2SAT problem. Each topping corresponds to a variable. When a topping is preferred with '+', we include in our clause. For preference '-', we include in the clause.
Solution
C++
#include <bits/stdc++.h>using namespace std;struct TwoSatSolver {int n_vars;int n_vertices;vector<vector<int>> adj, adj_t;vector<bool> used;vector<int> order, comp;vector<bool> assignment;
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CF | Easy | Show Tags2SAT | |||
CF | Easy | Show Tags2SAT, DFS, DSU | |||
CC | Easy | Show Tags2SAT, DSU, Greedy, Sliding Window | |||
Kattis | Easy | Show Tags2SAT | |||
AC | Normal | Show Tags2SAT | |||
CF | Hard | Show Tags2SAT, Binary Search, Trees | |||
CF | Hard | Show Tags2SAT, DFS |
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!