#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> c,d;
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) {
d[u] = 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]);
}
/*void dfs3(int v, int p, vector<int>& used, vector<int>& skip, vector<vector<int>>& adj, bool& ans) {
used[v] = 1;
for (auto u : adj[v]) {
if (skip[u]) continue;
if (!used[u]) {
dfs3(u,v,used,skip,adj,ans);
} else if (u != p) ans = true;
}
}*/
bool solvable(int v, vector<int>& comp, vector<vector<int>>& adj) {
vector<int> used(adj.size(),1), skip(adj.size(),1);
for (auto u: comp) {skip[u] = used[u] = 0;}
bool ans = false;
for (auto u: comp) {
int cnt = (u == v);
for (auto x : adj[u]) {
if (!skip[x]) cnt++;
}
ans |= cnt > 2;
}
//dfs3(v,-1,used,skip,adj,ans);
return ans;
}
vector<int> vis,p;
void dfs1(int v, vector<vector<int>>& adj) {
vis[v] = 1;
for (auto u: adj[v]) {
p[u] += 1;
if (!vis[u]) {
dfs1(u,adj);
}
}
}
vector<int> vis2, reach;
void dfs2(int v, vector<vector<int>>& adj) {
vis2[v] = 1;
if (d[v]) {
reach[v] = 1;
return;
}
for (auto u: adj[v]) {
if (!vis[u]) dfs2(u,adj);
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
vector<vector<int>> adj,cadj,comps;
adj.resize(N); c.resize(N); vis.resize(N); p.resize(N); d.resize(N); vis2.resize(N); reach.resize(N);
for (int i=0;i<M;i++) {
adj[U[i]].push_back(V[i]);
}
scc(adj,comps,cadj);
bool ans = false;
//checks if two path to same node in scc
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);
}
}
}
for (int i=0;i<N;i++) {
if (used[i] and c[i]) ans = true;
}
//checks if can reach scc in two places
dfs2(0,adj);
int cnt = 0;
for (int i=0;i<N;i++) {
cnt += reach[i];
}
if (cnt > 1) ans = true;
//if neither then at most one is reachable
if (ans == false and cnt == 1) {
int node = 0;
for (int i=0; i<N; i++) if (reach[i]) node = i;
vector<int> comp;
for (auto u: comps) {
for (auto v: u) {
if (v == node) comp = u;
}
}
if (comp.size() > 2) ans = solvable(node,comp,adj);
else {
if (comp[0] != node) swap(comp[0],comp[1]);
int nb = 0;
for (auto u : adj[node]) if (u == comp[1]) nb++;
ans = nb > 1;
}
}
return ans;
}
