CSES - Strongly Connected Edges

Time Complexity: $\mathcal O(N + M)$.

There are two cases when we can't make the graph strongly connected:

1. The graph isn't a single connected component.
2. The graph contains a bridge.

The first case can be checked with a simple DFS (i.e. check that it visits each node).

The second case can be checked in the same DFS using Tarjan's bridge-finding algorithm.

To construct the answer, set the direction of each edge to the direction in which we first traversed it in the DFS.

Copy
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<pair<int, int>> ans, graph[100001];
bool visited[100001], in_ans[200001];
int tin[100001], low[100001], timer = 0;

void dfs(int node = 1, int parent = 0) {
	visited[node] = true;