#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> c,d;
vector<bool> visited;
map<pair<int,int>,vector<int>> m;
vector<vector<int>> iadj;
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]);
m[{roots[v],roots[u]}].push_back(u);
} else {
iadj[v].push_back(u);
}
}
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;
}
return ans;
}
vector<int> vis,p;
vector<pair<int,int>> reach;
int dfs1(int v, vector<vector<int>>& adj) {
int cnt = 0;
vis[v] = 1;
for (auto u: adj[v]) {
p[u] += 1;
if (c[u]) {
reach.push_back({v,u});
}
if (!vis[u]) {
cnt += dfs1(u,adj);
}
}
return max(c[v],cnt);
}
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); iadj.resize(N); c.resize(N); vis.resize(N); p.resize(N); d.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
int diff = dfs1(0,cadj);
if (diff > 1) ans = true;
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;
}
if (ans == false) {
vector<int> get(N);
for (auto v : reach) {
for (auto u: m[v]) {
get[u] = 1;
}
}
for (int i=0;i<N;i++) {
get[i] += iadj[i].size();
}
ans = (*max_element(get.begin(),get.end())) > 2;
}
return ans;
}
