이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/BOI14_postmen
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 500007
#define MAXE 500007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
bool debug;
int N, M;
vii adjlist[MAXV];
int nxtEdge[MAXV];
int visited[MAXV], walked[MAXE];
int covered[MAXV];
vi cycle;
int svx;
void dfs(int u) {
visited[u] = 1;
while(nxtEdge[u] < sz(adjlist[u])) { /// still have an edge to walk
int j = nxtEdge[u];
int v = adjlist[u][j].ff, e = adjlist[u][j].ss;
nxtEdge[u]++;
if(walked[e]) continue;
walked[e] = 1;
if(visited[v]) { /// find a cycle
cycle.pb(u); svx = v; return;
}
dfs(v);
/// backtrack
cycle.pb(u);
if(svx != u) {
if(svx>0) return;
} else {
for(auto x : cycle) {
cout << x << " ";
visited[x] = 0; // can re-use in other cycle
covered[x] = 1;
}
cout << endl;
/// now use u as the starting point of a new cycle
visited[u] = 1;
svx = -1;
vi().swap(cycle);
}
}
}
int main() {
debug = false;
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> M;
for(int i=1; i<=M; i++) {
int a, b; cin >> a >> b;
adjlist[a].pb(mp(b,i)); adjlist[b].pb(mp(a, i));
}
for(int i=1; i<=N; i++)
if(!covered[i] && nxtEdge[i] < sz(adjlist[i])) dfs(i);
/// similar to Eulerian tour, prioritize pick edges first
if(debug) cout << endl << "EOL" << endl;
}
/**
10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |