Difference between revisions of "Eulerian Path"

Latest revision as of 15:21, 25 July 2018

int S[N << 1], top;
Edge edges[N << 1];
set<int> G[N];

void DFS(int u) {
    S[top++] = u;
    for (int eid: G[u]) {
        int v = edges[eid].get_other(u);
        G[u].erase(eid);
        G[v].erase(eid);
        DFS(v);
        return;
    }
}

void fleury(int start) {
    int u = start;
    top = 0; path.clear();
    S[top++] = u;
    while (top) {
        u = S[--top];
        if (!G[u].empty())
            DFS(u);
        else path.push_back(u);
    }
}

@@ Line 1: / Line 1: @@
 <syntaxhighlight lang='cpp'>
-struct Edge;
+int S[N << 1], top;
-typedef list<Edge>::iterator iter;
+Edge edges[N << 1];
+set<int> G[N];
-struct Edge {
+void DFS(int u) {
-    int next_vertex;
+    S[top++] = u;
-    iter reverse_edge;
+    for (int eid: G[u]) {
+         int v = edges[eid].get_other(u);
-    Edge(int next_vertex) : next_vertex(next_vertex) {}
+         G[u].erase(eid);
-};
+         G[v].erase(eid);
+         DFS(v);
-const int max_vertices =;
+        return;
-int num_vertices;
-list <Edge> adj[max_vertices]; // adjacency list
-vector<int> path;
-void find_path(int v) {
-    while (adj[v].size() > 0) {
-         int vn = adj[v].front().next_vertex;
-         adj[vn].erase(adj[v].front().reverse_edge);
-         adj[v].pop_front();
-         find_path(vn);
      }
-    path.push_back(v);
 }
-void add_edge(int a, int b) {
+void fleury(int start) {
-     adj[a].push_front(Edge(b));
+     int u = start;
-     iter ita = adj[a].begin();
+    top = 0; path.clear();
-    adj[b].push_front(Edge(a));
+     S[top++] = u;
-    iter itb = adj[b].begin();
+    while (top) {
-     ita->reverse_edge = itb;
+        u = S[--top];
-    itb->reverse_edge = ita;
+        if (!G[u].empty())
+            DFS(u);
+        else path.push_back(u);
+     }
 }
 </syntaxhighlight>

Difference between revisions of "Eulerian Path"

Latest revision as of 15:21, 25 July 2018

Navigation menu

Search