#ifndef Nhoksocqt1
#include "islands.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
vector<ii> adj[MAXN];
map<ii, int> cntEdge;
ii edge[2 * MAXN];
int low[MAXN], num[MAXN], tr[MAXN], numNode, numEdge;
bool dx[MAXN], dxt[2 * MAXN];
int getCntEdge(ii p) {
return (cntEdge.find(p) != cntEdge.end()) ? cntEdge[p] : 0;
}
void dfs(int u, int lastID = -1) {
dx[u] = 1;
tr[u] = lastID;
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it].fi), id(adj[u][it].se);
if(!dx[v])
dfs(v, id);
}
}
stack<int> st;
bool tarjan(int u) {
st.push(u);
low[u] = num[u] = ++num[numNode];
for (int it = 0; it < sz(adj[u]); ++it) {
int v(adj[u][it].fi), id(adj[u][it].se);
if(!dxt[id]) {
dxt[id] = 1;
if(!num[v]) {
if(tarjan(v))
return true;
low[u] = min(low[u], low[v]);
} else {
low[u] = min(low[u], num[v]);
}
}
}
if(low[u] == num[u]) {
int v, cnt(0);
do {
v = st.top(); st.pop();
low[v] = num[v] = 1e9+7;
++cnt;
} while(v != u);
return (cnt > 2);
}
return false;
}
#ifdef Nhoksocqt1
vector<int>
#else
variant<bool, vector<int>>
#endif // Nhoksocqt1
find_journey(int _N, int _M, vector<int> _U, vector<int> _V) {
numNode = _N, numEdge = _M;
for (int i = 0; i < numEdge; ++i) {
int u(_U[i]), v(_V[i]);
edge[i] = {u, v};
++cntEdge[ii(u, v)];
}
for (int i = 0; i < numEdge; ++i) {
int u(edge[i].u), v(edge[i].v);
if(getCntEdge(ii(u, v)) > 1)
adj[u].push_back(ii(v, i));
}
dfs(0);
int x(-1), y(-1), z(-1);
for (int i = 0; i < numNode; ++i) {
if(dx[i]) {
int t1(-1);
for (int it = 0; it < sz(adj[i]); ++it) {
int j(adj[i][it].fi);
if(edge[tr[i]].fi != j && getCntEdge(ii(j, i)) > 0) {
if(t1 < 0) {
t1 = j;
} else
if(t1 != j) {
x = i, y = t1, z = j;
break;
}
}
}
if(y >= 0)
break;
}
}
if(z >= 0) {
int idx_y(-1), idy_x(-1), idx_z(-1), idz_x(-1);
for (int i = 0; i < numEdge; ++i) {
int u(edge[i].fi), v(edge[i].se);
if(u == x && v == y)
idx_y = i;
if(u == y && v == x)
idy_x = i;
if(u == x && v == z)
idx_z = i;
if(u == z && v == x)
idz_x = i;
}
vector<int> ans, pf;
int u(x);
while(u != 0) {
ans.push_back(tr[u]);
u = edge[tr[u]].fi;
}
pf = ans;
reverse(ans.begin(), ans.end());
vector<int> p({idx_y, idy_x, idx_z, idz_x, idy_x, idx_y, idz_x, idx_z});
for (int it = 0; it < sz(p); ++it)
ans.push_back(p[it]);
for (int it = 0; it < sz(pf); ++it)
ans.push_back(pf[it]);
return ans;
}
for (int i = 0; i < numNode; ++i) {
if(!dx[i])
continue;
for (int it = 0; it < sz(adj[i]); ++it) {
int j(adj[i][it].fi);
if(edge[tr[i]].fi != j && getCntEdge(ii(i, j)) > 1 && getCntEdge(ii(j, i)) > 0) {
x = i, y = j;
break;
}
}
if(y >= 0)
break;
}
if(y >= 0) {
int idx_y_1(-1), idy_x(-1), idx_y_2(-1);
for (int i = 0; i < numEdge; ++i) {
int u(edge[i].fi), v(edge[i].se);
if(u == x && v == y) {
if(idx_y_1 < 0) {
idx_y_1 = i;
} else {
idx_y_2 = i;
}
}
if(u == y && v == x)
idy_x = i;
}
vector<int> ans, pf;
int u(x);
while(u != 0) {
ans.push_back(tr[u]);
u = edge[tr[u]].fi;
}
pf = ans;
reverse(ans.begin(), ans.end());
vector<int> p({idx_y_1, idy_x, idx_y_2, idx_y_1, idy_x, idx_y_2});
for (int it = 0; it < sz(p); ++it)
ans.push_back(p[it]);
for (int it = 0; it < sz(pf); ++it)
ans.push_back(pf[it]);
return ans;
}
for (int i = 0; i <= numNode; ++i)
low[i] = num[i] = 0;
if(tarjan(0))
return true;
#ifdef Nhoksocqt1
return {-1};
#else
return false;
#endif // Nhoksocqt1
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "islands"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> _U, _V;
int _N, _M;
cin >> _N >> _M;
_U.resize(_M), _V.resize(_M);
for (int i = 0; i < _M; ++i)
cin >> _U[i] >> _V[i];
vector<int> p = find_journey(_N, _M, _U, _V);
cout << "ANSWER: ";
if(sz(p) == 1 && p[0] == -1) {
cout << "NO\n";
} else {
for (int it = 0; it < sz(p); ++it)
cout << p[it] << ' ';
cout << '\n';
}
return 0;
}
#endif // Nhoksocqt1
Compilation message
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:93:23: error: 'ii' {aka 'struct std::pair<int, int>'} has no member named 'u'
93 | int u(edge[i].u), v(edge[i].v);
| ^
islands.cpp:93:37: error: 'ii' {aka 'struct std::pair<int, int>'} has no member named 'v'
93 | int u(edge[i].u), v(edge[i].v);
| ^
