#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> p, c, t, tl;
vector<vector<int>> g;
void dfs(int cur, int par){
if (!c.empty()) return;
if (p[cur] != -1) return;
p[cur] = par;
if (tl[cur] != -1){
c.push_back(cur);
c.push_back(tl[cur]);
while (cur != 0){
t.push_back(cur);
cur = p[cur];
}
t.push_back(cur);
reverse(t.begin(), t.end());
return;
}
for (int next : g[cur]){
if (next == par) continue;
if (p[next] != -1){
while (cur != next && cur != 0){
c.push_back(cur);
cur = p[cur];
}
c.push_back(cur);
while (cur != 0){
t.push_back(cur);
cur = p[cur];
}
t.push_back(cur);
reverse(c.begin(), c.end());
reverse(t.begin(), t.end());
return;
}
dfs(next, cur);
if (!c.empty()) return;
}
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
g.resize(N);
vector<vector<int>> v(N, vector<int>(N, -1));
tl.resize(N, -1);
for (int i=0; i<M; i+=2){
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
if (v[U[i]][V[i]] == -1) v[U[i]][V[i]] = i;
else {
tl[U[i]] = V[i];
tl[V[i]] = U[i];
}
v[V[i]][U[i]] = i+1;
}
p.resize(N, -1);
dfs(0, 0);
if (c.empty()) return false;
//return true;
/*for (int x : t) cout << x << " ";
cout << endl;
for (int x : c) cout << x << " ";
cout << endl;*/
vector<int> res;
for (int i=0; i<t.size()-1; i++) res.push_back(v[t[i]][t[i+1]]);
if (c.size() == 2){
res.push_back(v[c[0]][c[1]]);
res.push_back(v[c[0]][c[1]]^1);
res.push_back(v[c[1]][c[0]]^1);
res.push_back(v[c[0]][c[1]]);
res.push_back(v[c[0]][c[1]]^1);
res.push_back(v[c[1]][c[0]]^1);
}
else {
for (int i=0; i<c.size(); i++) res.push_back(v[c[i]][c[(i+1)%c.size()]]);
for (int i=c.size(); i>=1; i--) res.push_back(v[c[i%c.size()]][c[i-1]]);
for (int i=c.size(); i>=1; i--) res.push_back(v[c[i-1]][c[i%c.size()]]);
for (int i=0; i<c.size(); i++) res.push_back(v[c[(i+1)%c.size()]][c[i]]);
}
for (int i=(int)t.size()-1; i>=1; i--) res.push_back(v[t[i-1]][t[i]]);
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |