Distinct Routes

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

long long max_flow(vector<vector<int>> &adj, vector<vector<long long>> &capacity,
                   int source, int sink) {

	int n = adj.size();
	vector<int> parent(n, -1);

	auto reachable = [&]() -> bool {
		queue<int> q;
		q.push(source);
		while (!q.empty()) {
			int node = q.front();
			q.pop();
			for (auto y : adj[node]) {
				if (capacity[node][y] <= 0 || parent[y] != -1)
                    continue;
				parent[y] = node;
				q.push(y);
			}
		}
		return parent[sink] != -1;
	};

	long long flow = 0;

	while (reachable()) {

		int node = sink;
		long long current_flow = LONG_LONG_MAX;
		
        while (node != source) {
			current_flow = min(current_flow, capacity[parent[node]][node]);
			node = parent[node];
		}

		node = sink;

		while (node != source) {
			capacity[parent[node]][node] -= current_flow;
			capacity[node][parent[node]] += current_flow;
			node = parent[node];
		}

		flow += current_flow;
		fill(parent.begin(), parent.end(), -1);

	}

	return flow;

}

void dfs(vector<bool> &visited, stack<int> &path, vector<vector<int>> &adj, int current, int dest) {

    visited[current] = true;

    path.push(current);
 
    if (current == dest) {
        stack<int> q = path;
        cout << q.size() << endl;
        while (!q.empty()) {
            int c = q.top();
            q.pop();
            cout << c+1 << " ";
        }
        cout << endl;
    } else {
        for (int next : adj[current]) {
            if (!visited[next]) {
                dfs(visited, path, adj, next, dest);
            }
        }
    }

    path.pop();
    visited[current] = false;

}

int main() {

	int n, m;
	cin >> n >> m;

	vector<vector<long long>> capacity(n, vector<long long>(n, 0));
	vector<vector<int>> adj(n);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
		capacity[a][b] += 1;
	}

    vector<vector<long long>> init_cap = capacity;

    long long k = max_flow(adj, capacity, 0, n - 1);
	cout << k << endl;

    vector<vector<int>> adj2(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (capacity[i][j] == 0) continue;

            if (init_cap[i][j] != 0) continue;
            adj2[i].push_back(j);
            
        }
    }

    vector<bool> visited(n, false);
    vector<vector<int>> paths(k);

    stack<int> path;
    dfs(visited, path, adj2, n-1, 0);
    
}

/*
6 7
1 2
1 3
2 6
3 4
3 5
4 6
5 6
*/

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

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: ACCEPTED