#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> c;
vector<bool> visited;
void dfs(int v, vector<vector<int>> const& adj, vector<int> &output) {
visited[v] = true;
for (auto u : adj[v])
if (!visited[u])
dfs(u, adj, output);
output.push_back(v);
}
void scc(vector<vector<int>> const& adj, vector<vector<int>> &components, vector<vector<int>> &adj_cond) {
int n = adj.size();
components.clear(), adj_cond.clear();
vector<int> order; // will be a sorted list of G's vertices by exit time
visited.assign(n, false);
// first series of depth first searches
for (int i = 0; i < n; i++)
if (!visited[i])
dfs(i, adj, order);
// create adjacency list of G^T
vector<vector<int>> adj_rev(n);
for (int v = 0; v < n; v++)
for (int u : adj[v])
adj_rev[u].push_back(v);
visited.assign(n, false);
reverse(order.begin(), order.end());
vector<int> roots(n, 0); // gives the root vertex of a vertex's SCC
// second series of depth first searches
for (auto v : order)
if (!visited[v]) {
std::vector<int> component;
dfs(v, adj_rev, component);
components.push_back(component);
int root = *min_element(begin(component), end(component));
if (component.size() > 1) c[root] = 1;
for (auto u : component)
roots[u] = root;
}
// add edges to condensation graph
adj_cond.assign(n, {});
for (int v = 0; v < n; v++)
for (auto u : adj[v])
if (roots[v] != roots[u])
adj_cond[roots[v]].push_back(roots[u]);
}
vector<int> vis,p;
void dfs1(int v, vector<vector<int>> const& adj) {
vis[v] = 1;
for (auto u: adj[v]) {
p[u] += 1;
if (!vis[u]) {
dfs1(u,adj);
}
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
vector<vector<int>> adj,cadj,comp;
adj.resize(N); c.resize(N); vis.resize(N); p.resize(N);
for (int i=0;i<M;i++) {
adj[U[i]].push_back(V[i]);
}
scc(adj,comp,cadj);
dfs1(0,cadj);
queue<int> q; vector<int> used(N);
for (int i=0;i<N;i++)
if (p[i] > 1) {
q.push(i);
used[i] = true;
}
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : cadj[v]) {
if (!used[u]) {
used[u] = true;
q.push(u);
}
}
}
bool ans = false;
for (int i=0;i<N;i++) {
if (used[i] and c[i]) ans = true;
}
return ans;
}
