이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
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(neigh[nei] && !matrix[start][nei]) {
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();
}
}
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 start : graph[cur]) {
bfs(start);
}
for(int nei : graph[cur]) {
neigh[nei] = false;
}
neigh[cur] = 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... |