이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>
using namespace std;
const int N = 5e5 + 7;
struct Edge {
int u, v;
int alive;
Edge() {}
Edge(int u_, int v_) {
u = u_;
v = v_;
alive = 1;
}
};
int in[N];
int et[N];
Edge ed[N];
int g[2 * N];
int pnts[N];
int deg[N];
int rdeg[N];
int start[N];
int P = 0;
void dfs(int cur) {
for (; pnts[cur] < rdeg[cur]; pnts[cur]++) {
int ind = g[pnts[cur] + start[cur]];
if (ed[ind].alive) {
ed[ind].alive = 0;
int v = ed[ind].u;
if (v == cur) {
v = ed[ind].v;
}
dfs(v);
}
}
et[P] = cur;
P++;
}
int st[N];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> ed[i].u >> ed[i].v;
ed[i].alive = 1;
ed[i].u--;
ed[i].v--;
deg[ed[i].u]++;
deg[ed[i].v]++;
rdeg[ed[i].u]++;
rdeg[ed[i].v]++;
}
for (int i = 1; i < n; i++) {
start[i] = start[i - 1] + deg[i - 1];
}
for (int i = 0; i < m; i++) {
int u, v;
u = ed[i].u;
v = ed[i].v;
g[start[u] + deg[u] - 1] = i;
deg[u]--;
g[start[v] + deg[v] - 1] = i;
deg[v]--;
}
dfs(0);
int P2 = 0;
for (int i = 0; i < P; i++) {
int t = et[i];
if (in[t] > 0) {
while (true) {
in[st[P2 - 1]]--;
cout << st[P2 - 1] + 1 << ' ';
P2--;
if (st[P2] == t) break;
}
cout << '\n';
}
in[t]++;
st[P2] = t;
P2++;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |