Distinct Routes

input/code.cpp: In function 'void adjust_weights(std::vector<int>&, std::vector<std::vector<bool> >&)':
input/code.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 1; i < path.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <stack>
#include <functional>

std::vector<int> find_positive_path(int start, int end, std::vector<std::vector<int>> &edges, std::vector<std::vector<bool>> &used) {
    std::vector<bool> visited(edges.size(), false);

    std::function<std::vector<int>(int, int)> recurse = [&edges, &used, &visited, &recurse](int start, int end) -> std::vector<int> {
        if (start == end) return {end};
        
        visited[start] = true;
        std::vector<int> path;
        path.push_back(start);
        //std::cout << "Adding " << start+1 << std::endl;
        for (auto &edge : edges[start]) {
            if (visited[edge]) continue;
            if (used[start][edge]) continue;
            
            //std::cout << "Checking edge " << start+1 << " " << edge+1 << std::endl;
            std::vector<int> rescursed_path = recurse(edge, end);
            if (rescursed_path.size() > 0) {
                path.insert(path.end(), rescursed_path.begin(), rescursed_path.end());
                break;
            }
            //std::cout << "No valid path with " << edge+1 << std::endl;
        }

        if (path.size() == 1) {
            //std::cout << "Removing " << start+1 << std::endl;
            //visited[start] = false;
            return {};
        };
        //std::cout << "Found path" << std::endl;
        return path;
    };

    return recurse(start, end);
}

void adjust_weights(std::vector<int> &path, std::vector<std::vector<bool>> &used) {
    for (int i = 1; i < path.size(); ++i) {
        used[path[i-1]][path[i]] = true;
        used[path[i]][path[i-1]] = false;
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> edges(n);
    std::vector<std::vector<bool>> used(n, std::vector<bool>(n, true));
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        edges[a-1].push_back(b-1);
        edges[b-1].push_back(a-1);
        used[a-1][b-1] = false;
    }

    bool is_max_flow = false;
    uint64_t max_flow = 0;
    std::vector<std::vector<int>> paths;
    while(!is_max_flow) {
        std::vector<int> path = find_positive_path(0, n-1, edges, used);
        if (path.size() == 0) {
            is_max_flow = true;
            continue;
        }
        
        adjust_weights(path, used);

        paths.push_back(path);
        max_flow++;
    }

    std::cout << max_flow << std::endl;
    for (auto &path : paths) {
        std::cout << path.size() << std::endl;
        for (auto &node : path) {
            std::cout << node+1 << " ";
        }
        std::cout << std::endl;
    }
}

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

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER