#include "islands.h"
#include <iostream>
#include <map>
#include <variant>
#include <vector>
std::variant<bool, std::vector<int>> find_journey_connected(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> original_labels);
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
std::vector<std::vector<int>> canoesfrom(N);
for (int i = 0; i < M; ++i) canoesfrom[U[i]].push_back(i);
std::vector<bool> seen(N);
std::vector<int> stack = {0};
while (!stack.empty()) {
int node = stack.back();
stack.pop_back();
if (seen[node]) continue;
seen[node] = true;
for (int i : canoesfrom[node]) {
stack.push_back(V[i]);
}
}
std::vector<int> newu, newv, original_labels;
int newm = 0;
for (int i = 0; i < N; ++i) {
if (!seen[i]) continue;
for (int out : canoesfrom[i]) {
newu.push_back(U[out]);
newv.push_back(V[out]);
original_labels.push_back(out);
++newm;
}
}
return find_journey_connected(N, newm, newu, newv, original_labels);
}
// everything except line case works
std::variant<bool, std::vector<int>> find_journey_connected(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> original_labels) {
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
adj[U[i]].push_back(i);
}
std::vector<int> ans;
std::vector<int> seen(N, -1); // when did we go out from this node
auto dfs = [&](int node, auto dfs) -> int {
if (seen[node] != -1) {
ans.push_back(ans[seen[node]] ^ 1);
ans.push_back(ans[seen[node]]);
return ans[seen[node]];
}
seen[node] = ans.size();
for (int to : adj[node]) {
if (to & 1) continue;
ans.push_back(original_labels[to]);
int toflip = dfs(V[to], dfs);
if (toflip != -1) {
ans.push_back(original_labels[to] ^ (original_labels[to] == toflip));
return toflip;
}
ans.pop_back();
}
seen[node] = -1;
return -1;
};
int toflip = dfs(0, dfs);
if (toflip == -1) return false;
return ans;
}
