CSES. Police Chase

1.Problem

https://cses.fi/problemset/task/1695/

2.Idea

Find the max flow in the graph, and recover the minimum cut from the residual graph connectivity information.

3.Source

 int n, m;  
 Int adj[555][555];  
 Int oadj[555][555];  
 Int flow[555];  
 bool V[555];  
 int pa[555];  
 vector <pi> ans;  
 bool reachable() {  
      memset(V, false, sizeof V);  
      queue<int> Q;  
      Q.push(1); V[1] = 1;  
      while (!Q.empty()) {  
           int i = Q.front(); Q.pop();  
           RREP(j, n) if (adj[i][j] && !V[j]) {  
                V[j] = 1;  
                pa[j] = i;  
                Q.push(j);  
           }  
      }  
      return V[n];  
 }  
 void solve() {  
      cin >> n >> m;  
      RREP(i, n) RREP(j, n) adj[i][j] = oadj[i][j] = 0;  
      REP(i, m) {  
           Int a, b;  
           cin >> a >> b;  
           adj[a][b]++; adj[b][a]++;  
           oadj[a][b]++; oadj[b][a]++;  
      }  
      int v, u;  
      while (reachable()) {  
           Int flow = LINF;  
           for (v = n; v != 1; v = pa[v]) {  
                u = pa[v];  
                flow = min(flow, adj[u][v]);  
           }  
           for (v = n; v != 1; v = pa[v]) {  
                u = pa[v];  
                adj[u][v] -= flow;  
                adj[v][u] += flow;  
           }  
      }  
      reachable();  
      RREP(i, n) RREP(j, n) {  
           if (V[i] && !V[j] && oadj[i][j]) ans.push_back(pi(i, j));  
      }  
      cout << ans.size() << endl;  
      for (auto x : ans) cout << x.first << " " << x.second << endl;  
 }