이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <unordered_set>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef set<ll> sll;
typedef vector<vll> vvll;
typedef vector<sll> vsll;
typedef vector<bool> vb;
typedef unordered_set<ll> usll;
typedef vector<usll> vusll;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define sz(a) a.size()
const ll MAXN = 500000;
const ll MAXM = 500000;
ll N, M;
vll g[MAXN];
ll pr[MAXN] = {0};
bool onS[MAXN] = {0};
bool vis[MAXN] = {0};
ll e[2][MAXM];
ll getU(ll i, ll v) {
return (v == e[0][i]) ? e[1][i] : e[0][i];
}
bool DFS(ll cur) {
if (onS[cur]) {
// found axon
cout << cur + 1 << " ";
onS[cur] = false;
return true;
} else {
onS[cur] = true;
while (pr[cur] > 0) {
ll edge = g[cur][pr[cur] - 1];
pr[cur]--;
if (vis[edge]) {
continue;
}
ll nxt = getU(edge, cur);
vis[edge] = true;
if (DFS(nxt)) {
if (onS[cur]) {
cout << cur + 1 << " ";
onS[cur] = false;
return true;
} else {
onS[cur] = true;
cout << "\n";
}
}
}
return false;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
rep(i, 0, M) {
cin >> e[0][i] >> e[1][i];
e[0][i]--; e[1][i]--;
g[e[0][i]].pb(i);
pr[e[0][i]]++;
g[e[1][i]].pb(i);
pr[e[1][i]]++;
}
rep(i, 0, N) {
DFS(i);
}
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... |