QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#791889 | #995. 桥 | lizhu6 | RE | 0ms | 0kb | C++20 | 2.1kb | 2024-11-28 21:44:50 | 2024-11-28 21:44:54 |
answer
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cassert>
#include <numeric>
using namespace std;
typedef long long LL;
constexpr int mod = 998244353;
template <typename Tp1, typename Tp2> inline void cmax(Tp1 &A, const Tp2 &B) { if (A < B) A = B; return; }
template <typename Tp1, typename Tp2> inline void cmin(Tp1 &A, const Tp2 &B) { if (A > B) A = B; return; }
template <typename Tp1, typename Tp2, int mod = ::mod> inline void ad(Tp1 &A, const Tp2 &B) { A = (A + B) % mod; return; }
template <typename Tp1, typename Tp2, int mod = ::mod> inline void sb(Tp1 &A, const Tp2 &B) { A = (A + mod - B) % mod; return; }
constexpr int N = 100010;
int n, m;
vector<int> ans;
struct node
{
int next, to;
} e[N << 1]; int head[N], es = 1, dfn[N], low[N], tot;
void bian(int u, int v)
{
e[++es] = {head[u], v};
head[u] = es; return;
}
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++tot;
for (int i = head[u]; i; i = e[i].next)
if (const int v = e[i].to; !dfn[v])
{
tarjan(v, i);
cmin(low[u], low[v]);
if (low[v] > dfn[u])
ans.emplace_back((i | 1) ^ 1);
}
else if (i != fa && i != (fa ^ 1))
cmin(low[u], dfn[v]);
return;
}
struct par
{
par() = default;
par(int _x, int _y) : x(_x), y(_y) { }
bool operator<(const par Q) const { return x != Q.x ? x < Q.x : y < Q.y; }
bool operator==(const par Q) const { return x == Q.x && y == Q.y; }
bool operator>(const par Q) const { return x != Q.x ? x > Q.x : y > Q.y; }
int x, y;
};
vector<par> edge;
int main()
{
cin >> n >> m;
edge.resize(m + 1);
for (int i = 1; i <= m; i++)
{
cin >> edge[i].x >> edge[i].y;
if (edge[i].x == edge[i].y) continue;
bian(edge[i].x, edge[i].y);
bian(edge[i].y, edge[i].x);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i, 0);
sort(ans.begin(), ans.end());
for (auto th : ans)
{
th >>= 1;
cout << edge[th].x << ' ' << edge[th].y << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
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...