#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> #include <cstring> using namespace std; #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define _auto(var, x) typeof(x) var = (x) #define _auxforeach(it, b, e) for(_auto(it, b), _itend = e; it != _itend; ++it) #define foreach(it, r...) _auxforeach(it, r) typedef long long LLONG; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<bool> VB; typedef vector<VB> VVB; enum { INF = 1<<30 }; struct EulerianCycle { // (Closed Tour) // (OutDegree - InDegree) must be 0 for all vertices. VVI mtx; // input (manipulated) const int V; // input VI nextAdj; // private VVI answer; // output (list of stacks to be popped) /// mtx = binary adjacency matrix (directed graph) EulerianCycle(const VVI& mtx) : mtx(mtx), V(mtx.size()), nextAdj(V,0), answer(V) { // O(V²) foreach(i, 0,V) adjustNext(i); int nd = 0; while(nd < V) { if(nextAdj[nd] < V) depthFirstSearch(nd); else nd ++; } } /// Stores nodes from cycle in "output". void visit(VI& output) { // O(E) VVI stackOf = answer; int nd = 0; while(stackOf[nd].empty() and nd < V) nd++; if(nd == V) return; output.push_back(nd); while(!stackOf[nd].empty()) { int newNd = stackOf[nd].back(); output.push_back(newNd); stackOf[nd].pop_back(); nd = newNd; } } /// Stores nodes from cycle in "output". Starts at "firstNode". void visit(VI& output, int firstNode) { // O(E) visit(output); if(output.empty()) return; // All nodes "neighborless"... output.pop_back(); VI::iterator it = find(all(output), firstNode); if(it == output.end()) throw "Node has no neighbors!"; rotate(output.begin(), it, output.end()); output.push_back(output[0]); } void adjustNext(int nd) { // O(V) int& next = nextAdj[nd]; while(next < V and mtx[nd][next] == 0) next++; } void depthFirstSearch(int firstNd) { int nd = firstNd; bool first = true; while(nd != firstNd or first) { int adj = nextAdj[nd]; if(adj == V) throw "No Eulerian Cycle!"; answer[nd].push_back(adj); mtx[nd][adj] --; adjustNext(nd); nd = adj; first = false; } } }; #define bit(n, i) ((n & (1<<i))>0?1:0) #define upbit(n, i) (n |= (1<<i)) bool confere(int a, int b, int n){ for(int i=0; i<n-2; i++){ if(bit(b,n-1-i-1)!=bit(a,(-i+n-2-1))) return false; } return true; } int main(){ int n; while(true){ puts("Digite o tamanho ou zero pra sair:"); scanf("%d", &n); system("cls"); if(!n) break; puts("Tratando excessoes...\n"); if(n==1){ puts("O Drum e': 10\n"); continue; } puts("Nao existe excessoes...\n"); int v = (1<<(n-1)); //2 elevado a n-1 printf("Montando digrafo com %d vertices(2^%d)...\n\n", v, n-1); VVI mat(v, VI(v, 0)); VVI label(v, VI(v, -1)); puts("Criando arestas(A->B) onde os dois ultimos bits de A\nsao iguais aos dois primeiros bits de B...\n"); for(int i=0; i<v; i++){ for(int j=0; j<v; j++){ if(confere(i, j, n)){ mat[i][j]=1; label[i][j]=bit(j, 0); } } } puts("Buscando Ciclo Euleriano no digrafo, Complexidade O(V^2)\n"); EulerianCycle ec(mat); puts("Ciclo Euleriano ENCONTRADO! Gerando saida...\n"); VI ciclo; ec.visit(ciclo); //DESCOMENTE PARA VISUALIZAR O CICLO //for(int i=0; i<ciclo.size(); ++i) printf("%d ",ciclo[i]); puts("Reconstruindo ciclo e buscando labels..\n"); vector<int> drum; puts("O Drum e':"); for(int i=0; i<ciclo.size()-1; ++i){ printf("%d",label[ciclo[i]][ciclo[i+1]]); drum.push_back(label[ciclo[i]][ciclo[i+1]]); } puts("\n"); } }