This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 1000;
int n, m;
vector<int> graph[1 + maxn];
bool matrix[1 + maxn][1 + maxn];
bool neigh[1 + maxn];
int cur_mid;
int dist[1 + maxn];
int prv[1 + maxn];
int goal;
void bfs(int start) {
queue<int> q;
queue<int> all;
q.push(start);
all.push(start);
prv[start] = -1;
while(!q.empty()) {
int cur = q.front();
q.pop();
for(int nei : graph[cur]) {
if(prv[nei] == 0 && (!neigh[cur] || (cur == start && !neigh[nei]))) {
q.push(nei);
all.push(nei);
dist[nei] = dist[cur] + 1;
prv[nei] = cur;
if(nei == goal) {
while(nei != start) {
cout << nei << " ";
nei = prv[nei];
}
cout << start << " " << cur_mid << "\n";
exit(0);
}
}
}
}
while(!all.empty()) {
dist[all.front()] = prv[all.front()] = 0;
all.pop();
}
}
bool vis[1 + maxn];
vector<int> this_comp;
bool been[1 + maxn];
void do_bfs(int start) {
queue<int> q;
q.push(start);
vis[start] = true;
been[start] = true;
while(!q.empty()) {
int cur = q.front();
q.pop();
if(neigh[cur]) {
this_comp.pb(cur);
}
for(int nei : graph[cur]) {
if(!vis[nei]) {
q.push(nei);
vis[nei] = true;
been[nei] = true;
}
}
}
}
void try_for(int cur) {
cur_mid = cur;
if(graph[cur].empty()) {
return;
}
for(int nei : graph[cur]) {
neigh[nei] = true;
}
neigh[cur] = true;
for(int i = 1; i <= n; i++) {
if(!neigh[i] && !been[i]) {
do_bfs(i);
int m = (int) this_comp.size();
for(int j = 0; j < m; j++) {
for(int k = j + 1; k < m; k++) {
if(!matrix[this_comp[j]][this_comp[k]]) {
goal = this_comp[k];
bfs(this_comp[j]);
}
}
}
for(int x : this_comp) {
been[x] = vis[x] = false;
}
}
}
for(int nei : graph[cur]) {
neigh[nei] = false;
}
neigh[cur] = false;
for(int i = 1; i <= n; i++) {
vis[i] = false;
been[i] = false;
}
}
void solve() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
graph[a].pb(b);
graph[b].pb(a);
matrix[a][b] = matrix[b][a] = true;
}
for(int i = 1; i <= n; i++) {
try_for(i);
}
cout << "no\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# | 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... |