QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#53577 | #2341. Dead-End Detector | not_so_organic | AC ✓ | 225ms | 26452kb | C++11 | 2.7kb | 2022-10-05 13:34:35 | 2022-10-05 13:34:37 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <ctype.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
const int N = 1000005;
int head[N], to[N * 2], nxt[N * 2], pre[N], deg[N], DEG[N], cnt = 1;
void add(int u, int v) {
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
pre[cnt] = u;
}
int n, m;
void work1() {
queue<int>Q;
bool vis[N] = {0};
for (int i = 1; i <= n; i++)
if (deg[i] == 1)
Q.push(i), vis[i] = 1;
while (!Q.empty()) {
int now = Q.front();
Q.pop();
for (int i = head[now]; i; i = nxt[i]) {
int v = to[i];
if (!vis[v] && (--deg[v]) == 1)
Q.push(v), vis[v] = 1;
}
}
}
bool vis[N];
void work2() {
queue<int>Q;
for (int i = 1; i <= n; i++)
if (deg[i] >= 2)
Q.push(i), vis[i] = 1;
while (!Q.empty()) {
int now = Q.front();
Q.pop();
for (int i = head[now]; i; i = nxt[i]) {
int v = to[i];
if (!vis[v] && deg[v] == 1)
Q.push(v), vis[v] = 1;
}
}
}
vector<pair<int, int>>ans;
int main() {
n = read(), m = read();
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
add(u, v);
add(v, u);
DEG[u]++, DEG[v]++;
deg[u]++, deg[v]++;
}
work1();
work2();
// for(int i=1;i<=n;i++)
// printf("%d %d %d\n",deg[i],DEG[i],vis[i]);
for (int i = 1; i <= cnt; i += 2) {
int x = pre[i], y = to[i];
if (vis[x] || vis[y]) {
// printf("!!!%d %d\n",x,y);
if ((deg[x] == 1 && deg[y] == 1) || (deg[x] > 1 && deg[y] > 1))
continue;
if (deg[x] == 1)
ans.push_back(make_pair(y, x));
else
ans.push_back(make_pair(x, y));
} else if (!vis[x] && !vis[y]) {
if (DEG[y] == 1)
ans.push_back(make_pair(y, x));
if (DEG[x] == 1)
ans.push_back(make_pair(x, y));
}
}
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (int i = 0; i < (int)ans.size(); i++)
printf("%d %d\n", ans[i].first, ans[i].second);
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 3ms
memory: 4688kb
Test #2:
score: 0
Accepted
time: 2ms
memory: 4556kb
Test #3:
score: 0
Accepted
time: 86ms
memory: 24348kb
Test #4:
score: 0
Accepted
time: 3ms
memory: 4660kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 4680kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 4680kb
Test #7:
score: 0
Accepted
time: 3ms
memory: 4712kb
Test #8:
score: 0
Accepted
time: 4ms
memory: 4740kb
Test #9:
score: 0
Accepted
time: 2ms
memory: 4756kb
Test #10:
score: 0
Accepted
time: 3ms
memory: 4760kb
Test #11:
score: 0
Accepted
time: 3ms
memory: 4680kb
Test #12:
score: 0
Accepted
time: 2ms
memory: 4744kb
Test #13:
score: 0
Accepted
time: 26ms
memory: 16396kb
Test #14:
score: 0
Accepted
time: 61ms
memory: 16452kb
Test #15:
score: 0
Accepted
time: 175ms
memory: 24864kb
Test #16:
score: 0
Accepted
time: 190ms
memory: 25868kb
Test #17:
score: 0
Accepted
time: 202ms
memory: 26448kb
Test #18:
score: 0
Accepted
time: 184ms
memory: 26436kb
Test #19:
score: 0
Accepted
time: 3ms
memory: 4680kb
Test #20:
score: 0
Accepted
time: 3ms
memory: 4804kb
Test #21:
score: 0
Accepted
time: 3ms
memory: 4764kb
Test #22:
score: 0
Accepted
time: 36ms
memory: 12276kb
Test #23:
score: 0
Accepted
time: 66ms
memory: 24440kb
Test #24:
score: 0
Accepted
time: 40ms
memory: 22332kb
Test #25:
score: 0
Accepted
time: 95ms
memory: 22128kb
Test #26:
score: 0
Accepted
time: 43ms
memory: 24440kb
Test #27:
score: 0
Accepted
time: 90ms
memory: 24388kb
Test #28:
score: 0
Accepted
time: 63ms
memory: 24344kb
Test #29:
score: 0
Accepted
time: 64ms
memory: 24340kb
Test #30:
score: 0
Accepted
time: 82ms
memory: 20240kb
Test #31:
score: 0
Accepted
time: 164ms
memory: 20156kb
Test #32:
score: 0
Accepted
time: 114ms
memory: 25888kb
Test #33:
score: 0
Accepted
time: 225ms
memory: 25896kb
Test #34:
score: 0
Accepted
time: 146ms
memory: 22616kb
Test #35:
score: 0
Accepted
time: 177ms
memory: 24328kb
Test #36:
score: 0
Accepted
time: 161ms
memory: 24376kb
Test #37:
score: 0
Accepted
time: 152ms
memory: 24260kb
Test #38:
score: 0
Accepted
time: 194ms
memory: 24824kb
Test #39:
score: 0
Accepted
time: 150ms
memory: 22932kb
Test #40:
score: 0
Accepted
time: 134ms
memory: 23832kb
Test #41:
score: 0
Accepted
time: 150ms
memory: 23124kb
Test #42:
score: 0
Accepted
time: 146ms
memory: 23532kb
Test #43:
score: 0
Accepted
time: 136ms
memory: 23592kb
Test #44:
score: 0
Accepted
time: 205ms
memory: 26452kb
Test #45:
score: 0
Accepted
time: 207ms
memory: 26400kb