10320 | 2024. 03. 30 17:52:02 | szil | Pletykálkodás | cpp17 | Elfogadva 100/100 | 405ms | 7252 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 7001;
vector<int> g[MAXN];
vector<pair<int, int>> ans1, ans2;
bool vis[MAXN];
void dfs(int u) {
vis[u] = true;
for (int v : g[u]) {
if (!vis[v]) {
dfs(v);
ans1.emplace_back(u, v);
}
}
}
void print_ans() {
int k = ans1.size() + ans2.size();
cout << k << "\n";
for (auto [u, v] : ans1) {
cout << u << " " << v << "\n";
}
for (auto [u, v] : ans2) {
cout << u << " " << v << "\n";
}
}
void case1() {
dfs(1);
ans2 = ans1;
ans2.pop_back();
reverse(ans2.begin(), ans2.end());
print_ans();
exit(0);
}
void case2(vector<int> cyc) {
for (int i : cyc) vis[i] = true;
for (int i : cyc) {
dfs(i);
}
ans2 = ans1;
ans1.emplace_back(cyc[0], cyc[1]);
ans1.emplace_back(cyc[2], cyc[3]);
ans1.emplace_back(cyc[0], cyc[3]);
ans1.emplace_back(cyc[1], cyc[2]);
reverse(ans2.begin(), ans2.end());
print_ans();
exit(0);
}
vector<int> mp[MAXN];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
if (n == 1) {
cout << "0\n";
return 0;
}
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
for (int i = 1; i <= n; i++) {
for (int u : g[i]) {
for (int v : g[u]) {
mp[v].emplace_back(u);
}
}
for (int u = 1; u <= n; u++) {
if (u == i) continue;
if (mp[u].size() >= 2) {
case2({i, mp[u][0], u, mp[u][1]});
}
}
for (int u = 1; u <= n; u++) {
mp[u].clear();
}
}
case1();
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 2540 KiB | ||||
2 | Elfogadva | 3ms | 2820 KiB | ||||
3 | Elfogadva | 4ms | 3276 KiB | ||||
subtask2 | 9/9 | ||||||
4 | Elfogadva | 3ms | 3312 KiB | ||||
5 | Elfogadva | 3ms | 3196 KiB | ||||
6 | Elfogadva | 3ms | 3196 KiB | ||||
subtask3 | 13/13 | ||||||
7 | Elfogadva | 133ms | 4744 KiB | ||||
8 | Elfogadva | 131ms | 4908 KiB | ||||
9 | Elfogadva | 130ms | 5096 KiB | ||||
subtask4 | 16/16 | ||||||
10 | Elfogadva | 7ms | 4804 KiB | ||||
11 | Elfogadva | 7ms | 4808 KiB | ||||
12 | Elfogadva | 7ms | 4720 KiB | ||||
subtask5 | 25/25 | ||||||
13 | Elfogadva | 3ms | 3756 KiB | ||||
14 | Elfogadva | 3ms | 3764 KiB | ||||
15 | Elfogadva | 3ms | 4012 KiB | ||||
16 | Elfogadva | 3ms | 3972 KiB | ||||
17 | Elfogadva | 3ms | 4232 KiB | ||||
18 | Elfogadva | 3ms | 4444 KiB | ||||
19 | Elfogadva | 3ms | 4396 KiB | ||||
subtask6 | 13/13 | ||||||
20 | Elfogadva | 4ms | 4656 KiB | ||||
21 | Elfogadva | 4ms | 4920 KiB | ||||
22 | Elfogadva | 4ms | 4952 KiB | ||||
23 | Elfogadva | 19ms | 5484 KiB | ||||
24 | Elfogadva | 16ms | 5120 KiB | ||||
25 | Elfogadva | 16ms | 5040 KiB | ||||
26 | Elfogadva | 6ms | 5240 KiB | ||||
subtask7 | 24/24 | ||||||
27 | Elfogadva | 12ms | 6828 KiB | ||||
28 | Elfogadva | 12ms | 6740 KiB | ||||
29 | Elfogadva | 12ms | 6840 KiB | ||||
30 | Elfogadva | 294ms | 7252 KiB | ||||
31 | Elfogadva | 349ms | 7064 KiB | ||||
32 | Elfogadva | 405ms | 6708 KiB | ||||
33 | Elfogadva | 402ms | 6552 KiB | ||||
34 | Elfogadva | 375ms | 6468 KiB | ||||
35 | Elfogadva | 17ms | 6692 KiB | ||||
36 | Elfogadva | 39ms | 6652 KiB | ||||
37 | Elfogadva | 9ms | 6496 KiB |