Distinct Routes

input/code.cpp: In function 'long long int findPath(std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<std::vector<long long int> >&, std::vector<bool>&, long long int, long long int, long long int)':
input/code.cpp:16:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (long long i=0;i<g[node].size();i++){
      |                        ~^~~~~~~~~~~~~~~
input/code.cpp: In function 'bool checkPaths(std::vector<long long int>)':
input/code.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (;i<path.size();i++){
      |               ~^~~~~~~~~~~~
input/code.cpp:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vect...

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<vector<long long>> pathList(0, vector<long long>(0));

long long findPath(vector<vector<pair<long long,long long>>>& g, vector<vector<long long>> & rev, vector<bool>& visited, long long node, long long sink, long long flow){
    if (node==sink){
        return flow;
    }

    visited[node]=true;

    for (long long i=0;i<g[node].size();i++){
        long long next=g[node][i].first;
        long long cap=g[node][i].second;

        if (!visited[next] && cap>0){
            long long pushed = findPath(g, rev, visited, next, sink, min(flow, cap));

            if (pushed>0){
                g[node][i].second-=pushed;
                g[next][rev[node][i]].second+=pushed;
                return pushed;
            }
        }
    }
    return 0;
}

long long maxFlow(vector<vector<pair<long long,long long>>> & g, vector<vector<long long>>& rev, long long source, long long sink){
    long long totalFlow=0;

    while (true){
        vector<bool> visited(g.size(), false);
        long long pushed = findPath(g, rev, visited, source, sink, LLONG_MAX);
        if (pushed==0){
            break;
        }
        totalFlow+=pushed;
    }
    return totalFlow;
}

bool checkPaths(vector<long long> path){
    for (auto & p: pathList){
        if (p.size()!=path.size()) {
            continue;
        }
        int i=0;
        for (;i<path.size();i++){
            if (p[i]!=path[i]){
                break;
            }
        }
        if (i==path.size()){
            return false;
        }
    }
    return true;
}

bool findPaths(vector<vector<pair<long long, long long>>> & g, vector<long long>& path, vector<bool> & visited, long long node, long long start, long long sink, vector<bool> &visitedTmp){
    if (node==sink){
        if (checkPaths(path)) {

            for (long long i: path){
                visited[i]=true;
            }
            pathList.push_back(path);
            return true;
        } else {
            return false;
        }
    }
    if (visitedTmp[node]){
        return false;
    }
    if (visited[node]&& node!=start){
        return false;
    }
    visitedTmp[node]=true;
    path.push_back(node);
    for (auto next: g[node]){
        if (next.second==0 && !visited[next.first]){
            if (findPaths(g, path, visited, next.first, start, sink, visitedTmp)){
                return true;
            }
            
        }
    }
    visitedTmp[node]=false;
    path.pop_back();
    return false;
}

int main(){
    long long n, m;
    cin >> n >> m;
    //node, capacity
    vector<vector<pair<long long,long long>>> g(n+1, vector<pair<long long,long long>>(0));
    vector<vector<long long>> rev(n+1, vector<long long>(0));
    for (long long i=0;i<m;i++){
        long long from, to;
        cin >> from >> to;


        rev[from].push_back(g[to].size());
        rev[to].push_back(g[from].size());

        g[from].push_back({to,1});
        g[to].push_back({from,0});

    }

    long long paths=maxFlow(g, rev, 1, n);

    cout << paths << '\n';
    vector<bool> visited(n+1);
    for (long long i=0;i<paths;i++){
        vector<long long> path(0);
        vector<bool> visitedTmp(n+1);
        findPaths(g, path, visited, 1, 1, n, visitedTmp);
    }

    for (auto & p : pathList){
        cout << p.size()+1 << '\n';
        for (int i: p){
            cout << i << ' ';
        }
        cout << n << '\n';
    }
    return 0;

}

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: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER