이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int N, M;
vvi adj;
vvi adj2;
bool possible;
vi cnt[2];
vvi CNT[2];
vi ans, tmpans;
vi bw;
vi BW[2];
bool usable;
void dfsBW(int v, int p)
{
bw[v] = !bw[p];
BW[bw[v]].push_back(v);
for (int u : adj[v])
if (u != p)
dfsBW(u, v);
}
void dfs(int v, int p)
{
cnt[0][v] = 1;
cnt[1][v] = 0;
for (int u : adj[v])
if (u != p)
{
dfs(u, v);
cnt[0][v] += cnt[1][u];
cnt[1][v] += cnt[0][u];
}
}
void dfsAns(int v, int p)
{
tmpans.push_back(v); // safe besuchen
vi todo;
for (int u : adj2[v])
if (u != p)
todo.push_back(u);
dfs(v, v);
if (sz(todo) <= 1)
{
int idx = 0;
for (int u : adj[v])
if (u != p && (todo.empty() || u != todo[0]) && cnt[1][u] > 0)
{
assert(cnt[0][u] == 1);
if (idx > 0)
tmpans.push_back(v);
tmpans.push_back(u);
++idx;
}
if (sz(todo) == 1)
{
if (idx > 0)
tmpans.push_back(v);
dfsAns(todo[0], v);
}
}
else
{
// must be 2
usable = false;
// assert(false);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
if (M > N - 1)
{
cout << "NO\n";
return 0;
}
adj.resize(N);
for (int i = 0, a, b; i < M; ++i)
{
cin >> a >> b;
--a, --b;
adj[a].push_back(b), adj[b].push_back(a);
}
bw.assign(N, 0);
dfsBW(0, 0);
adj2.resize(N);
possible = true;
cnt[0].resize(N), cnt[1].resize(N);
for (int v = 0; v < N; ++v)
{
dfs(v, v);
for (int u : adj[v])
if (cnt[0][u] >= 2)
adj2[v].push_back(u);
if (sz(adj2[v]) > 2)
possible = false;
}
if (possible)
{
cout << "YES\n";
int color = 0;
if (sz(BW[!color]) < sz(BW[color]))
color = !color;
if (BW[color].empty())
{
ans.push_back(0);
}
else
{
for (int v = 0; v < N; ++v)
{
if (sz(adj2[v]) <= 1)
{
usable = true;
tmpans.clear();
dfsAns(v, v);
if (usable && (ans.empty() || sz(ans) > sz(tmpans)))
swap(tmpans, ans);
}
}
int n = sz(ans);
for (int i = n - 1; i >= 0; --i)
ans.push_back(ans[i]);
}
cout << sz(ans) << '\n';
for (int x : ans)
cout << x + 1 << " ";
cout << '\n';
}
else
cout << "NO\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |