이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int max_N = int(1E5) + 5;
constexpr int max_M = int(6E6) + 5;
constexpr int S = 2450;
int N, M;
std::queue<int> adj[max_N];
int cur, cedg, cnedg;
int A[S], B[S];
struct DSU {
std::vector<int> f;
DSU(int n) : f(n) {
std::iota(f.begin(), f.end(), 0);
}
int get(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool unite(int a, int b) {
a = get(a), b = get(b);
if (a == b) {
return false;
}
f[a] = b;
return true;
}
bool same(int a, int b) {
return get(a) == get(b);
}
int operator[](int x) {
return get(x);
}
} belong(max_N);
std::pair<int, int> edg[3 * max_N], nedg[3 * max_N];
std::stack<int> stk;
int tin[max_N], low[max_N], comp[max_N], timer, n;
void tarjan(int v, int pr) {
stk.emplace(v);
tin[v] = low[v] = timer++;
while (!adj[v].empty()) {
int i = adj[v].front();
adj[v].pop();
if (i == pr) {
continue;
}
int u = v ^ belong[nedg[i].first] ^ belong[nedg[i].second];
if (tin[u] == -1) {
tarjan(u, i);
low[v] = std::min(low[v], low[u]);
} else if (comp[u] == -1) {
low[v] = std::min(low[v], tin[u]);
}
}
if (low[v] == tin[v]) {
int u;
do {
u = stk.top();
stk.pop();
comp[u] = n;
} while (u != v);
++n;
}
}
void recalc() {
n = 0;
timer = 0;
for (int i = 0; i < N; ++i) {
tin[i] = low[i] = comp[i] = -1;
}
cnedg = 0;
for (int i = 0; i < cedg; ++i) {
assert(cnedg < 3 * max_N);
nedg[cnedg] = edg[i];
adj[belong[edg[i].first]].emplace(cnedg);
adj[belong[edg[i].second]].emplace(cnedg);
++cnedg;
}
cedg = 0;
for (int i = 0; i < cur; ++i) {
if (belong[A[i]] != belong[B[i]]) {
assert(cnedg < 3 * max_N);
nedg[cnedg] = {A[i], B[i]};
adj[belong[A[i]]].emplace(cnedg);
adj[belong[B[i]]].emplace(cnedg);
++cnedg;
}
}
cur = 0;
for (int i = 0; i < N; ++i) {
if (tin[belong[i]] == -1) {
tarjan(belong[i], -1);
}
}
for (int i = 0; i < cnedg; ++i) {
if (comp[belong[nedg[i].first]] != comp[belong[nedg[i].second]]) {
assert(cedg < 3 * max_N);
edg[cedg] = nedg[i];
++cedg;
} else {
belong.unite(nedg[i].first, nedg[i].second);
}
}
#ifdef DEBUG
for (int i = 0; i < N; ++i) {
std::cerr << belong[i] << " \n"[i == N - 1];
}
for (int i = 0; i < cedg; ++i) {
std::cerr << edg[i].first + 1 << ' ' << edg[i].second + 1 << '\n';
}
std::cerr << '\n';
#endif
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> N >> M;
while (M--) {
std::cin >> A[cur] >> B[cur];
--A[cur], --B[cur];
++cur;
if (cur == S) {
recalc();
}
}
recalc();
for (int i = 0; i < cedg; ++i) {
std::cout << edg[i].first + 1 << ' ' << edg[i].second + 1 << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |