이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//
// Created by 42kangaroo on 30/08/2024.
//
#include "bits/stdc++.h"
using namespace std;
using g_t = vector<set<int>>;
void dfs(int n, int p, int d, g_t& g, vector<pair<int,int>>& st, vector<int>& de) {
de[n] = d;
vector<int> up;
st.push_back({n, de[n] + 1});
for (auto e: g[n]) {
if (e == p || de[e] > de[n]) continue;
if (de[e] != -1) {
st[de[e]].second++;
up.push_back(de[e]);
}
else dfs(e, n, d + 1, g, st, de);
}
std::sort(up.begin(), up.end());
int i = de[n] - 2;
for (; i >= 0; ++i) {
if (up.empty() || up.back() != i) break;
up.pop_back();
}
i--;
for (auto e: g[n]) {
if (e == p || de[e] > de[n]) continue;
if (de[e] != -1) {
if (i > de[e] || st[de[e]].second < de[n]) {
int j = de[n] - 1;
for (; j > de[e]; --j) {
if (g[st[j].first].find(n) == g[st[j].first].end() || g[st[j].first].find(e) == g[st[j].first].end()) break;
}
int act = n;
while (act != j) {
cout << act + 1<< " ";
int be = act;
for (auto f: g[act]) {
if (de[f] < de[be] && de[f] >= de[j] ) {
be = f;
}
}
act = be;
}
act = j;
while (act != e) {
cout << act + 1 << " ";
int be = act;
for (auto f: g[act]) {
if (de[f] < de[be] && de[f] >= de[e] ) {
be = f;
}
}
act = be;
}
cout << e + 1;
exit(0);
}
}
}
for (auto e: g[n]) {
if (e == p || de[e] > de[n]) continue;
if (de[e] != -1) {
st[de[e]].second--;
}
}
st.pop_back();
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
g_t g(n);
for (int i = 0; i < m; ++i) {
int a, b; cin >> a >> b;
g[--a].insert(--b);
g[b].insert(a);
}
vector<int> de(n, -1);
vector<pair<int,int>> st;
for (int i = 0; i < n; ++i) {
if (de[i] == -1) {
dfs(i, i, 0, g, st, de);
}
}
cout << "no";
}
# | 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... |
# | 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... |