Distinct Routes

input/code.cpp: In member function 'int MaxFlow::dfs(int, int, int)':
input/code.cpp:46:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int &cid = ptr[v]; cid < graph[v].size(); cid++) {
      |                                ~~~~^~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int i=0; i<path.size(); i++){
      |                      ~^~~~~~~~~~~~
input/code.cpp:124:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             cout << path[i] << (i < path.size()-1 ? ' ' : '\n');
      |                                 ~~^~~~~~~~~~~~~~~

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

struct Edge {
    int to;
    int rev;
    int cap;
};

class MaxFlow {
public:
    int n;
    vector<vector<Edge>> graph;
    vector<int> level;
    vector<int> ptr;

    MaxFlow(int nodes) : n(nodes), graph(nodes + 1), level(nodes + 1, -1), ptr(nodes + 1, 0) {}

    void add_edge(int from, int to, int cap) {
        Edge a = {to, (int)graph[to].size(), cap};
        Edge b = {from, (int)(graph[from].size()), 0};
        graph[from].push_back(a);
        graph[to].push_back(b);
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(!q.empty()) {
            int v = q.front(); q.pop();
            for(auto &e : graph[v]) {
                if(e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                    if(e.to == t) break;
                }
            }
        }
        return level[t] != -1;
    }

    int dfs(int v, int t, int pushed) {
        if(v == t) return pushed;
        for(int &cid = ptr[v]; cid < graph[v].size(); cid++) {
            Edge &e = graph[v][cid];
            if(e.cap > 0 && level[e.to] == level[v] + 1) {
                int tr = dfs(e.to, t, min(pushed, e.cap));
                if(tr > 0) {
                    graph[v][cid].cap -= tr;
                    graph[e.to][e.rev].cap += tr;
                    return tr;
                }
            }
        }
        return 0;
    }

    int max_flow_func(int s, int t) {
        int flow = 0;
        while(bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while(int pushed = dfs(s, t, INT32_MAX)) {
                flow += pushed;
            }
        }
        return flow;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;

    MaxFlow mf(n);

    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        mf.add_edge(a, b, 1);
    }

    int max_flow = mf.max_flow_func(1, n);

    vector<vector<int>> paths;

    vector<vector<Edge>> residual_graph = mf.graph;

    function<bool(int, int, vector<int>&, vector<vector<Edge>> &)> find_path = [&](int u, int t, vector<int> &path, vector<vector<Edge>> &res_g) -> bool {
        if(u == t){
            return true;
        }
        for(auto &e : res_g[u]){
            if(e.cap == 0) {
                e.cap = -1;
                auto &rev_edge = res_g[e.to][e.rev];
                rev_edge.cap = -1;
                path.push_back(e.to);
                if(find_path(e.to, t, path, res_g)){
                    return true;
                }
                path.pop_back();
                e.cap = 0;
                rev_edge.cap = 0;
            }
        }
        return false;
    };
    for(int i=0; i<max_flow; i++){
        vector<int> path;
        path.push_back(1);
        bool found = find_path(1, n, path, residual_graph);
        if(found){
            paths.push_back(path);
        }
    }
    cout << max_flow << "\n";
    for(auto &path : paths){
        cout << path.size() << "\n";
        for(int i=0; i<path.size(); i++){
            cout << path[i] << (i < path.size()-1 ? ' ' : '\n');
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER