#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int max_N = int(1000) + 5;
int N, M;
std::vector<int> adj[max_N], cdj[max_N];
std::vector<int> stk;
int tin[max_N], low[max_N], belong[max_N], siz[max_N], timer, nc;
void dfs1(int v, int pr) {
stk.emplace_back(v);
low[v] = tin[v] = ++timer;
for (auto u : adj[v]) {
if (u == pr) {
continue;
}
if (low[u] == 0) {
dfs1(u, v);
low[v] = std::min(low[v], low[u]);
} else if (belong[u] == 0) {
low[v] = std::min(low[v], tin[u]);
}
}
if (low[v] == tin[v]) {
++nc;
int u;
do {
u = stk.back();
stk.pop_back();
belong[u] = nc;
++siz[nc - 1];
} while (u != v);
}
}
void solve_seperated_diameter_local() {
for (int n = 1; n <= 10; ++n) {
std::vector<int> dp(1 << n, -1);
dp[0] = 0;
auto dfs = [&](auto&& self, int mask) -> int {
if (dp[mask] != -1) {
return dp[mask] == -2 ? n : dp[mask];
}
dp[mask] = -2;
int ans = n + 100;
for (int i = 0; i < n; ++i) {
int nmask = 0;
for (int j = 0; j < n; ++j) {
if (mask >> j & 1 && i != j) {
if (j - 1 >= 0) nmask |= (1 << (j - 1));
if (j + 1 < n) nmask |= (1 << (j + 1));
}
}
ans = std::min(ans, self(self, nmask) + 1);
}
return dp[mask] = ans;
};
int ans = dfs(dfs, (1 << n) - 1);
std::cout << n << ' ' << ans << '\n';
}
}
std::vector<int> find_diameter() {
std::vector<int> dist(N);
auto dfs = [&](auto&& self, int v, int pr) -> void {
for (auto u : adj[v]) {
if (u == pr) {
continue;
}
dist[u] = dist[v] + 1;
self(self, u, v);
}
};
dfs(dfs, 0, 0);
int root = std::max_element(dist.begin(), dist.end()) - dist.begin();
dist.assign(N, 0);
dfs(dfs, root, root);
root = std::max_element(dist.begin(), dist.end()) - dist.begin();
dist.assign(N, 0);
dfs(dfs, root, root);
int leaf = std::max_element(dist.begin(), dist.end()) - dist.begin();
std::vector<int> stk;
auto find = [&](auto&& self, int v, int pr) -> void {
stk.emplace_back(v);
if (v == leaf) {
return;
}
for (auto u : adj[v]) {
if (u == pr) {
continue;
}
self(self, u, v);
if (stk.back() == leaf) {
return;
}
}
stk.pop_back();
};
find(find, root, root);
return stk;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// solve_seperated_diameter_local();
std::cin >> N >> M;
for (int i = 0; i < M; ++i) {
int A, B;
std::cin >> A >> B;
--A, --B;
adj[A].emplace_back(B);
adj[B].emplace_back(A);
}
dfs1(0, 0);
if (nc != N) {
std::cout << "NO\n";
return 0;
}
auto dia = find_diameter();
std::vector<int> dep(N, -1);
for (auto u : dis) {
dep[u] = 0;
que.emplace(u);
}
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto u : adj[v]) {
if (dep[u] != -1) {
continue;
}
dep[u] = dep[v] + 1;
que.emplace(u);
}
}
for (int i = 0; i < N; ++i) {
if (dep[i] >= 2) {
std::cout << "NO\n";
return 0;
}
}
std::cout << "YES\n";
std::cout << "1\n1\n";
return 0;
}
Compilation message
newspapers.cpp: In function 'int main()':
newspapers.cpp:137:19: error: 'dis' was not declared in this scope; did you mean 'dia'?
137 | for (auto u : dis) {
| ^~~
| dia
newspapers.cpp:139:9: error: 'que' was not declared in this scope
139 | que.emplace(u);
| ^~~
newspapers.cpp:141:13: error: 'que' was not declared in this scope
141 | while (!que.empty()) {
| ^~~
