#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 7;
const int INF = (int) 1e9 + 7;
int n, m, dist[N], par[N], t[N];
bool valid[N];
vector<int> g[N];
void clr() {
for (int i = 1; i <= n; i++) t[i] = i;
}
int get_root(int a) {
if (t[a] == a) return a;
return t[a] = get_root(t[a]);
}
void join(int a, int b) {
a = get_root(b);
b = get_root(b);
t[a] = b;
}
bool is_edge(int a, int b) {
int low = 0, high = (int) g[a].size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (g[a][mid] == b) {
return 1;
}
if (g[a][mid] < b) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return 0;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
///freopen ("input.txt", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
sort(g[i].begin(), g[i].end());
}
for (int root = 1; root <= n; root++) {
clr();
for (int i = 1; i <= n; i++) {
valid[i] = 1;
}
valid[root] = 0;
for (auto &v : g[root]) {
valid[v] = 0;
}
for (int i = 1; i <= n; i++) {
if (valid[i]) {
for (auto &j : g[i]) {
if (valid[j]) {
join(i, j);
if (i < j) {
// cout << " : " << i << " and " << j << "\n";
}
}
}
}
}
int v1_sol, v2_sol;
bool found = 0;
for (auto &v1 : g[root]) {
for (auto &v2 : g[root]) {
if (found) break;
if (v1 == v2) break;
if (is_edge(v1, v2)) continue;
assert(valid[v1] == 0 && valid[v2] == 0);
set<int> s1, s2;
for (auto &i : g[v1]) {
if (valid[i]) s1.insert(get_root(i));
}
for (auto &i : g[v2]) {
if (valid[i]) s2.insert(get_root(i));
}
bool good = 0;
for (auto &guy : s1) {
if (s2.count(guy)) {
good = 1;
}
}
if (good) {
found = 1;
v1_sol = v1;
v2_sol = v2;
}
}
}
if (!found) continue;
int v1 = v1_sol, v2 = v2_sol;
/// cout << root << " : " << v1 << " " << v2 << "\n";
for (int i = 1; i <= n; i++) {
dist[i] = INF;
par[i] = 0;
}
dist[root] = -1;
for (auto &v : g[root]) {
if (v != v1 && v != v2) {
dist[v] = -1;
}
}
queue<int> q;
dist[v1] = 0;
q.push(v1);
while (!q.empty()) {
int a = q.front();
q.pop();
for (auto &b : g[a]) {
if (dist[b] == INF) {
dist[b] = 1 + dist[a];
par[b] = a;
q.push(b);
}
}
}
assert(dist[v1] != -1);
if (dist[v2] != -1 && dist[v2] != INF) {
while (v2 != v1) {
cout << v2 << " ";
v2 = par[v2];
}
cout << v1 << " " << root << "\n";
exit(0);
} else {
assert(0);
}
}
cout << "no\n";
exit(0);
}
Compilation message
indcyc.cpp: In function 'int main()':
indcyc.cpp:143:21: warning: 'v2_sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
143 | cout << v1 << " " << root << "\n";
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
340 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
408 KB |
Expected integer, but "no" found |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
340 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
824 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
718 ms |
1340 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
