#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();
}
}
vector<int> this_comp;
bool been[1 + maxn];
void do_bfs(int start) {
queue<int> q;
q.push(start);
been[start] = true;
while(!q.empty()) {
int cur = q.front();
q.pop();
if(neigh[cur]) {
this_comp.pb(cur);
continue;
}
for(int nei : graph[cur]) {
if(!been[nei]) {
q.push(nei);
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] = false;
}
this_comp.clear();
}
}
for(int nei : graph[cur]) {
neigh[nei] = false;
}
neigh[cur] = false;
for(int i = 1; i <= n; i++) {
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();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
4 ms |
860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
1884 KB |
Output is correct |
2 |
Correct |
3 ms |
1624 KB |
Output is correct |
3 |
Correct |
91 ms |
2000 KB |
Output is correct |
4 |
Correct |
49 ms |
1880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1628 KB |
Output is correct |
2 |
Correct |
39 ms |
1628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
1880 KB |
Output is correct |
2 |
Correct |
10 ms |
1780 KB |
Output is correct |
3 |
Correct |
9 ms |
2140 KB |
Output is correct |
4 |
Correct |
101 ms |
2204 KB |
Output is correct |