QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#42762 | #995. 桥 | Qingyu | WA | 130ms | 23456kb | C++23 | 906b | 2022-08-03 17:41:02 | 2022-08-03 17:41:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 50;
int n, m, dfn[N], low[N], tot, ex[N], ey[N];
int bridge[N];
vector<pair<int, int>> G[N];
void tarjan(int x, int e) {
dfn[x] = low[x] = ++tot;
int cnt = 0;
for (auto [y, i] : G[x]) {
if (!dfn[y]) {
tarjan(y, i);
low[x] = min(low[x], low[y]);
if (dfn[x] < low[y]) {
bridge[i] = true;
}
}
else if (e != i) low[x] = min(low[x], dfn[y]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
G[x].emplace_back(y, i);
G[y].emplace_back(x, i);
ex[i] = x, ey[i] = y;
}
for (int i = 1; i <= n; ++i)
if (!dfn[i])
tarjan(i, i);
for (int i = 1; i <= m; ++i) if (bridge[i])
cout << ex[i] << ' ' << ey[i] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 130ms
memory: 23456kb
input:
24942 387166 12556 21443 22404 16376 11073 24296 1535 11968 23745 2818 5073 12731 22550 14761 24118 12008 22695 18979 15118 13639 2080 8721 692 22578 22581 15267 9278 4127 7457 21674 17693 23448 10949 23429 9700 6009 14140 5064 7742 15164 17336 1662 18903 9760 17645 19575 6540 11942 11 4937 15282 10...
output:
16461 14146 16462 4200 16461 17395 16632 7933 16461 9707 16462 22491 16461 19413 16462 18586 16461 24247 16461 18426 16461 16814 16461 5033 16461 10924 16602 11305 16461 9218 16461 6887 16461 2630 16461 19970 16461 24516 16461 6688 16461 807 16461 10383 16461 18710 16461 5516 16461 20812 16462 13565...
result:
wrong output format Extra information in the output file