이 제출은 이전 버전의 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()
ll N, M;
vsll g;
vll S;
vb onS;
vvll paths;
bool DFS(ll cur) {
if (onS[cur]) {
// found axon
paths.pb(vll());
paths.back().pb(cur);
onS[cur] = false;
return true;
} else {
onS[cur] = true;
S.pb(cur);
for (sll::iterator nxt = g[cur].begin(); nxt != g[cur].end();) {
g[*nxt].erase(cur);
if (DFS(*nxt)) {
if (onS[cur]) {
paths.back().pb(cur);
onS[cur] = false;
S.pop_back();
g[cur].erase(nxt);
return true;
} else {
onS[cur] = true;
}
}
nxt++;
g[cur].erase(prev(nxt));
}
S.pop_back();
return false;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
g.resize(N);
rep(i, 0, M) {
ll tmpa, tmpb;
cin >> tmpa >> tmpb;
tmpa--; tmpb--;
g[tmpa].insert(tmpb);
g[tmpb].insert(tmpa);
}
onS.resize(N, false);
rep(i, 0, N) {
DFS(i);
}
for (vvll::iterator path = paths.begin(); path != paths.end(); path++) {
for (vll::iterator itr = path->begin(); itr != path->end(); itr++) {
cout << (*itr) + 1 << " ";
}
cout << "\n";
}
cout << flush;
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... |