QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#777532 | #2341. Dead-End Detector | wxhtzdy | AC ✓ | 353ms | 81532kb | C++20 | 2.0kb | 2024-11-24 02:57:08 | 2024-11-24 02:57:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<pair<int, int>> res;
vector<bool> skip(n);
{
vector<bool> was(n);
bool ok;
vector<int> ver;
function<void(int, int)> Dfs = [&](int v, int pv) {
ver.push_back(v);
was[v] = true;
for (int u : g[v]) {
if (u == pv) {
continue;
}
if (!was[u]) {
Dfs(u, v);
} else {
ok = false;
}
}
};
for (int i = 0; i < n; i++) {
if (was[i]) {
continue;
}
ok = true;
ver.clear();
Dfs(i, i);
if (ok) {
for (int i : ver) {
skip[i] = true;
if (int(g[i].size()) == 1) {
res.emplace_back(i, g[i][0]);
}
}
}
}
}
{
vector<int> deg(n);
for (int i = 0; i < n; i++) {
deg[i] = int(g[i].size());
}
vector<int> que;
for (int i = 0; i < n; i++) {
if (skip[i]) {
continue;
}
if (deg[i] == 1) {
que.push_back(i);
}
}
for (int b = 0; b < int(que.size()); b++) {
int i = que[b];
for (int j : g[i]) {
deg[j] -= 1;
if (deg[j] == 1) {
que.push_back(j);
}
}
}
vector<int> in(n);
for (int i : que) {
in[i] = true;
}
for (int i = 0; i < n; i++) {
if (skip[i] || !in[i]) {
continue;
}
for (int j : g[i]) {
if (!in[j]) {
res.emplace_back(j, i);
}
}
}
}
cout << int(res.size()) << '\n';
sort(res.begin(), res.end());
for (auto& p : res) {
cout << p.first + 1 << " " << p.second + 1 << '\n';
}
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 3612kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
Test #3:
score: 0
Accepted
time: 162ms
memory: 81456kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 3604kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3548kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3760kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 3608kb
Test #8:
score: 0
Accepted
time: 5ms
memory: 18832kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 3612kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 3624kb
Test #11:
score: 0
Accepted
time: 1ms
memory: 3756kb
Test #12:
score: 0
Accepted
time: 1ms
memory: 3832kb
Test #13:
score: 0
Accepted
time: 44ms
memory: 7320kb
Test #14:
score: 0
Accepted
time: 49ms
memory: 7848kb
Test #15:
score: 0
Accepted
time: 222ms
memory: 36544kb
Test #16:
score: 0
Accepted
time: 207ms
memory: 40452kb
Test #17:
score: 0
Accepted
time: 223ms
memory: 45992kb
Test #18:
score: 0
Accepted
time: 214ms
memory: 44672kb
Test #19:
score: 0
Accepted
time: 1ms
memory: 3844kb
Test #20:
score: 0
Accepted
time: 1ms
memory: 3644kb
Test #21:
score: 0
Accepted
time: 1ms
memory: 3832kb
Test #22:
score: 0
Accepted
time: 64ms
memory: 13808kb
Test #23:
score: 0
Accepted
time: 246ms
memory: 62780kb
Test #24:
score: 0
Accepted
time: 96ms
memory: 81532kb
Test #25:
score: 0
Accepted
time: 256ms
memory: 79028kb
Test #26:
score: 0
Accepted
time: 92ms
memory: 81376kb
Test #27:
score: 0
Accepted
time: 240ms
memory: 81456kb
Test #28:
score: 0
Accepted
time: 264ms
memory: 81508kb
Test #29:
score: 0
Accepted
time: 245ms
memory: 81448kb
Test #30:
score: 0
Accepted
time: 100ms
memory: 38328kb
Test #31:
score: 0
Accepted
time: 165ms
memory: 38496kb
Test #32:
score: 0
Accepted
time: 103ms
memory: 40360kb
Test #33:
score: 0
Accepted
time: 206ms
memory: 40424kb
Test #34:
score: 0
Accepted
time: 353ms
memory: 75956kb
Test #35:
score: 0
Accepted
time: 229ms
memory: 37096kb
Test #36:
score: 0
Accepted
time: 254ms
memory: 43416kb
Test #37:
score: 0
Accepted
time: 244ms
memory: 52352kb
Test #38:
score: 0
Accepted
time: 235ms
memory: 37212kb
Test #39:
score: 0
Accepted
time: 212ms
memory: 36736kb
Test #40:
score: 0
Accepted
time: 223ms
memory: 47868kb
Test #41:
score: 0
Accepted
time: 221ms
memory: 37104kb
Test #42:
score: 0
Accepted
time: 249ms
memory: 35296kb
Test #43:
score: 0
Accepted
time: 220ms
memory: 36032kb
Test #44:
score: 0
Accepted
time: 200ms
memory: 45264kb
Test #45:
score: 0
Accepted
time: 191ms
memory: 45352kb