Distinct Routes

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<int> to, cap;
vector<vector<int>> adj;

void addEdge(int a, int b){
  adj[a].push_back(to.size());
  to.push_back(b);
  cap.push_back(1);

  adj[b].push_back(to.size());
  to.push_back(a);
  cap.push_back(0);
}

int bfs(){
  vector<int> parentEdge(n + 1, -1);
  vector<bool> vis(n + 1, false);
  queue<int> q;
  q.push(1);
  vis[1] = true;

  while(!q.empty() && !vis[n]){
    int v = q.front(); q.pop();
    for(int e : adj[v]){
      if(cap[e] > 0 && !vis[to[e]]){
        vis[to[e]] = true;
        parentEdge[to[e]] = e;
        q.push(to[e]);
      }
    }
  }

  if(!vis[n]) return 0;

  for(int v = n; v != 1; v = to[parentEdge[v] ^ 1]){
    int e = parentEdge[v];
    cap[e] -= 1;
    cap[e ^ 1] += 1;
  }
  return 1;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> m;
  adj.assign(n + 1, {});

  for(int i = 0; i < m; ++i){
    int a, b;
    cin >> a >> b;
    addEdge(a, b);
  }

  int flow = 0;
  while(bfs()) flow++;

  vector<int> ptr(n + 1, 0);
  vector<vector<int>> paths;

  for(int i = 0; i < flow; ++i){
    vector<int> path = {1};
    int v = 1;
    while(v != n){
      while(ptr[v] < (int)adj[v].size()){
        int e = adj[v][ptr[v]++];
        if(e % 2 == 0 && cap[e] == 0){
          v = to[e];
          path.push_back(v);
          break;
        }
      }
    }
    paths.push_back(path);
  }

  cout << flow << endl;
  for(auto& p : paths){
    cout << p.size() << endl;
    for(size_t i = 0; i < p.size(); ++i)
      cout << p[i] << (i + 1 < p.size() ? " " : "\n");
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED