Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
finding eulerian cycle
// -----------------------------
// オイラー閉路を線形時間Oで探すプログラム
// -----------------------------
// ----------------------------------------------------------------------------
// 下らない個人的な何かここから
// ----------------------------------------------------------------------------
#include "bits/stdc++.h"
#ifdef WINT_MIN
#define __MAI
#endif
using namespace std;
typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;
#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;
#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;
#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}
#define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}
#define ALL(v) (v).begin(),(v).end()
#define repeat(l) for(auto cnt=0;cnt<(l);++cnt)
#define upto(l,r) for(auto cnt=l;cnt<=r;++cnt)
#define downto(r,l) for(auti cnt=r;cnt>=l;--cnt)
#define BIGINT 0x7FFFFFFF
#define E107 1000000007ll
#define PI 3.1415926535897932384626433832795
void printbit(int u) { if (u == 0)cout << 0; else { int s = 0, k = 0; for (; 0<u; u >>= 1, k++)s = (s << 1) | (u & 1); for (; 0<k--; s >>= 1)cout << (s & 1); } }template<typename T1, typename T2>
ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }
#define TIME chrono::system_clock::now()
#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())
namespace {
std::chrono::system_clock::time_point t;
void tic() { t = TIME; }
void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - t)); }
std::chrono::system_clock::time_point tle = TIME;
#ifdef __MAI
void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); }
#else
#define safe_tle(k) ;
#endif
}
#ifndef __MAI
namespace {
class MaiScanner {
public:
template<typename T>
void input_integer(T& var) {
var = 0;
T sign = 1;
int cc = getchar_unlocked();
for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
if (cc == '-') sign = -1;
for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
var = (var << 3) + (var << 1) + cc - '0';
var = var*sign;
}
void ign() { getchar_unlocked(); }
MaiScanner& operator>>(int& var) {
input_integer<int>(var);
return *this;
}
MaiScanner& operator>>(long long& var) {
input_integer<long long>(var);
return *this;
}
};
}
MaiScanner scanner;
#else
#define scanner cin
#endif
// ----------------------------------------------------------------------------
// 下らない個人的な何かここまで
// ----------------------------------------------------------------------------
class UndirectedGraphE {
public:
size_t n;
struct Edge {
int u, v;
Edge(int from = 0, int to = 0) :u(from), v(to) {}
int to(int _v) const { return _v == v ? u : v; }
};
vector<vector<int>> vertex_to;
vector<Edge> edge;
UndirectedGraphE(int n, int m = 5010) :n(n), vertex_to(n) { edge.reserve(m); }
void connect(int from, int to) {
vertex_to[from].push_back(edge.size()); // toto
vertex_to[to].push_back(edge.size()); // fromfrom
edge.emplace_back(from, to);
}
size_t degree(int v) const{
return vertex_to[v].size();
}
void resize(size_t _n) {
n = _n;
vertex_to.resize(_n);
}
};
// オイラー閉路が存在するかどうか?
// グラフが連結であるという前提で動作する.
bool isExistEulerianTrail(const UndirectedGraphE& g) {
repeat(g.n) {
if (g.degree(cnt) % 2) return false;
}
return g.n != 0;
}
// オイラー閉路を見つける.
// オイラー閉路が存在する前提で動作する.
// 返る値は,頂点ID,辺ID,頂点ID,辺ID,...,頂点IDの形式で格納される.
// 先頭と末尾の頂点IDは同一のものになる.
vector<int> findEulerialCycle(const UndirectedGraphE& graph) {
// 辺に割り当てたグループ番号
vector<int> group(graph.edge.size());
int lastgroupNo = 0;
// グラフを複数の閉路で分割し,その各閉路ごとにグループ番号を割り当てる.
// 多重ループだが,最も深い部分の処理回数は(2|E|)である.
for (int idx = 0; idx < graph.edge.size(); ++idx) {
if (group[idx] != 0) continue;
group[idx] = ++lastgroupNo;
int tail = graph.edge[idx].v;
int v = graph.edge[idx].u;
bool running = true;
while (running) {
running = false;
for (int ie : graph.vertex_to[v]) {
if (group[ie] == 0) {
group[ie] = lastgroupNo;
v = graph.edge[ie].to(v);
running = true;
break;
}
}
}
}
vector<int> result;
{
// 既にその辺は歩きました(必要ないけれど,何ステップ目にその辺を歩いたかも保持する)
vector<int> walked(graph.edge.size());
// その閉路のグループ番号は見たことがあります
vector<int> checked(lastgroupNo + 1);
// グループ番号を見た順に積んでいくスタック
stack<int> ss;
int step = 1;
// 0番目の辺を選択し,その辺を始点とする.
int tail = graph.edge[0].v;
int v = graph.edge[0].u;
ss.push(group[0]);
checked[group[0]] = true;
// 最初に選んだ辺を結果に入れる.
result.push_back(graph.edge[0].v);
result.push_back(0);
result.push_back(v);
walked[0] = step++;
int stat = 1;
while (stat) {
stat = 0;
vector<int> dic(lastgroupNo + 1); // 配列の初期化だってO(1)とみなすのです
for (int ie : graph.vertex_to[v]) {
if (walked[ie]) continue;
int g = group[ie];
if (!checked[g]) {
// 初めて見たグループ番号ならばその辺を選んで次の頂点へ
checked[g] = true;
ss.push(g);
walked[ie] = step++;
v = graph.edge[ie].to(v);
result.push_back(ie);
result.push_back(v);
stat = 2; break;
}
else {
// 既知のグループ番号ならば,グループ番号から辺番号を参照出来るようにしておく.
if (!dic[g]) {
dic[g] = ie + 1;
stat = 1;
}
}
}
// 初めて見たグループ番号が無いケース
if (stat == 1) {
// stackの一番上に積み重なっているグループ番号が,頂点に接続した辺の中に含まれないなら除去.
while (!dic[ss.top()]) {
ss.pop();
assert(!ss.empty()); // バグ対策用
}
// stackの一番上に積み重なっているグループ番号を使う.
int ie = dic[ss.top()] - 1;
walked[ie] = step++;
v = graph.edge[ie].to(v);
result.push_back(ie);
result.push_back(v);
}
}
}
return result;
}
// dic配列の初期化をO(1)とみなしたくない人用
// その他色々最適化した
vector<int> findEulerialTrail_2(const UndirectedGraphE& graph) {
vector<int> group(graph.edge.size());
int lastgroupNo = 0;
for (int idx = 0; idx < graph.edge.size(); ++idx) {
if (group[idx] != 0) continue;
group[idx] = ++lastgroupNo;
int tail = graph.edge[idx].v;
int v = graph.edge[idx].u;
bool running = true;
while (running) {
running = false;
for (int ie : graph.vertex_to[v]) {
if (group[ie] == 0) {
group[ie] = lastgroupNo;
v = graph.edge[ie].to(v);
running = true;
break;
}
}
}
}
vector<int> result;
vector<int> checked(lastgroupNo + 1);
stack<int> ss;
int tail = graph.edge[0].v;
int v = graph.edge[0].u;
ss.push(group[0]);
checked[group[0]] = true;
result.push_back(graph.edge[0].v);
result.push_back(0);
result.push_back(v);
group[0] = -1;
int stat = 1;
// (ループの外に出た!)
vector<pair<int,int>> dic(lastgroupNo + 1);
for (int step = 1; stat != 0; ++step) {
stat = 0;
for (int ie : graph.vertex_to[v]) {
if (group[ie] < 0) continue;
int g = group[ie];
if (!checked[g]) {
checked[g] = true;
ss.push(g);
group[ie] = -1;
v = graph.edge[ie].to(v);
result.push_back(ie);
result.push_back(v);
stat = 2; break;
}
else {
if (dic[g].first != step) {
dic[g].first = step;
dic[g].second = ie;
stat = 1;
}
}
}
if (stat == 1) {
while (dic[ss.top()].first != step) {
ss.pop();
assert(!ss.empty()); // バグ対策用
}
int ie = dic[ss.top()].second;
group[ie] = -1;
v = graph.edge[ie].to(v);
result.push_back(ie);
result.push_back(v);
}
}
return result;
}
int main() {
int n;
scanf("%d;", &n);
UndirectedGraphE graph(n);
for (int a, b, i = 0; scanf("%d,%d/", &a, &b)>0; i++) {
graph.connect(a, b);
}
assert(isExistEulerianTrail(graph));
vector<int> result = findEulerialCycle_2(graph);
debugv(result);
return 0;
}
// stdin:
// 7;1,6/4,1/4,5/5,6/2,3/2,3/6,3/0,1/3,5/1,2/3,4/5,2/3,4/6,0
// 9;0,1/1,2/2,3/3,4/2,4/0,2/1,5/5,6/1,6/1,7/7,8/1,8
//
@n=200
@mrange=(20..50).to_a
@cycle=90
result=[]
na=(0..(@n-1)).to_a
na.inject(na[-1]){|s,e|
result<<[s,e]
s=e
}
@cycle.times{
lp=na.sample(@mrange.sample)
lp.inject(lp[-1]){|s,e|
result<<[s,e]
s=e
}
}
result.shuffle!
printf("%d;%s",@n,result.map{|e|e*","}*"/")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment