CSES - Police Chase

Time Complexity: $\mathcal O(N^3)$

First, we run a max flow algorithm on the graph. Then, we run another BFS from node $1$. If node $a$ is reachable but node $b$ is not and there was an edge $a\rightarrow b$, then we know that edge must be removed.

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

using ll = long long;
using vi = vector<int>;
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)