CF 2080A - Strong Connectivity Strikes Back

Rating: 3200
Tags: *special, constructive algorithms, graphs
Solve time: 56s
Verified: yes

Solution

Problem Understanding

We are given a directed graph with n vertices and m edges. The task is to determine the minimum number of edges that need to be added to make the graph strongly connected. A graph is strongly connected if there is a directed path from every vertex to every other vertex.

The input consists of n and m, followed by m pairs of integers representing the directed edges between vertices. The output is a single integer: the minimum number of edges needed to achieve strong connectivity.

The constraints imply that n can be up to 10^5 and m up to 10^5. This rules out algorithms with quadratic complexity such as repeatedly checking reachability from each vertex. We need a linear or near-linear solution.

Edge cases include:

Already strongly connected graphs. For example, a triangle with edges 1→2, 2→3, 3→1. The answer should be 0.
Graphs with isolated vertices. For instance, n=3 and no edges. Each vertex is its own strongly connected component, so multiple edges must be added.
Graphs with a single vertex. The answer is always 0 regardless of edges.

Approaches

A brute-force approach would consider each pair of vertices and check if a path exists between them. For a graph with n vertices, this could require O(n^3) operations using Floyd-Warshall or repeated BFS/DFS from each vertex. This is too slow for n=10^5.

The key insight comes from strongly connected components (SCCs). Each SCC is internally strongly connected. The graph of SCCs forms a Directed Acyclic Graph (DAG). To make the original graph strongly connected, we only need to connect SCCs in the DAG so that it becomes a single SCC.

Let sources be the number of SCCs with no incoming edges, and sinks be the number of SCCs with no outgoing edges. Then, the minimum number of edges required is max(sources, sinks). This works because each source needs an incoming edge, each sink needs an outgoing edge, and the DAG must be connected in a cycle.

The standard algorithm to compute SCCs efficiently is Kosaraju's algorithm or Tarjan's algorithm, both of which run in O(n + m) time.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n^3)	O(n^2)	Too slow
SCC + DAG Analysis	O(n + m)	O(n + m)	Accepted

Algorithm Walkthrough

Read the number of vertices n and edges m, and construct the adjacency list of the graph.
Run Kosaraju's algorithm to find all strongly connected components. This involves a DFS pass to record finishing times, a graph transpose, and a DFS in reverse order of finishing times.
Build the condensed graph of SCCs, where each SCC is a node and edges exist if there is any edge between two SCCs in the original graph.
Count the number of SCCs with no incoming edges (sources) and no outgoing edges (sinks).
If the number of SCCs is 1, the graph is already strongly connected. Otherwise, return max(sources, sinks).

Why it works: SCCs partition the graph into components that cannot be broken further. Connecting the sources and sinks in the SCC DAG ensures every component can reach every other. The maximum of sources and sinks guarantees that no component remains disconnected either way.

Python Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def kosaraju_scc(n, adj):
    visited = [False] * n
    order = []

    def dfs(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs(v)
        order.append(u)

    for u in range(n):
        if not visited[u]:
            dfs(u)

    transpose = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            transpose[v].append(u)

    comp_id = [-1] * n
    def dfs_rev(u, label):
        comp_id[u] = label
        for v in transpose[u]:
            if comp_id[v] == -1:
                dfs_rev(v, label)

    label = 0
    for u in reversed(order):
        if comp_id[u] == -1:
            dfs_rev(u, label)
            label += 1

    return comp_id, label

def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u - 1].append(v - 1)

    comp_id, num_scc = kosaraju_scc(n, adj)
    if num_scc == 1:
        print(0)
        return

    in_deg = [0] * num_scc
    out_deg = [0] * num_scc
    for u in range(n):
        for v in adj[u]:
            if comp_id[u] != comp_id[v]:
                out_deg[comp_id[u]] += 1
                in_deg[comp_id[v]] += 1

    sources = sum(1 for deg in in_deg if deg == 0)
    sinks = sum(1 for deg in out_deg if deg == 0)
    print(max(sources, sinks))

if __name__ == "__main__":
    main()

The first DFS computes finishing times, the second DFS on the transposed graph labels SCCs. Counting in-degree and out-degree for each SCC identifies sources and sinks. Be careful with 1-based input; we convert it to 0-based indexing.

Worked Examples

Sample Input 1:

3 2
1 2
2 3

Step	order	transpose	comp_id	sources	sinks
DFS	[0, 1, 2]	[[ ], [0], [1]]	[0,1,2]	1	1

Explanation: Each node is its own SCC. Node 1 has no incoming edges (source), node 3 has no outgoing edges (sink). Minimum edges = max(1, 1) = 1.

Sample Input 2:

Step	order	transpose	comp_id	sources	sinks
DFS	[0,1,2]	[[2], [0], [1]]	[0,0,0]	0	0

All nodes are in one SCC. No edges needed. Output is 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Kosaraju’s algorithm traverses all vertices and edges twice.
Space	O(n + m)	Adjacency lists and auxiliary arrays for visited, order, comp_id.

For n ≤ 10^5 and m ≤ 10^5, this fits comfortably in 1-2 seconds.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        main()
    return out.getvalue().strip()

# provided samples
assert run("3 2\n1 2\n2 3\n") == "1", "sample 1"
assert run("3 3\n1 2\n2 3\n3 1\n") == "0", "sample 2"

# custom cases
assert run("1 0\n") == "0", "single node"
assert run("4 0\n") == "4", "all isolated"
assert run("4 3\n1 2\n2 3\n3 4\n") == "1", "chain of nodes"
assert run("4 4\n1 2\n2 3\n3 4\n4 1\n") == "0", "already cyclic"

Test input	Expected output	What it validates
1 0	0	Single vertex case
4 0	4	Multiple isolated vertices
4 3 chain	1	Minimum edges to connect chain
4 4 cycle	0	Already strongly connected

Edge Cases

For a graph with multiple isolated vertices, n=4, m=0, each vertex is its own SCC. We have 4 sources and 4 sinks. Maximum = 4, which correctly gives the number of edges needed to form a cycle connecting all vertices.

For a single vertex with self-loop, n=1, m=1, Kosaraju identifies 1 SCC. Both sources and sinks are 0, returning 0 as expected.

This solution correctly handles all boundary conditions and unusual topologies.