UASCO 3.3 Riding The Fence

This is a problem to find Euler Path of the graph. As this is an undirected graph, the Euler Path exists iff:

• All graph vertices have even degree. Or,
• All graph vertices have even degree, except two vertices have odd degree. And these two vertices will be start / end of the Euler Path.

This problem explicitly stated that the Euler Path existing, so no need to do the test to find out if the path exists or not. Instead, the job is to find out the exact path with the constraint that vertices should be sequenced in ascending order. There are a couple of well studied algorithm can solve the Euler Path finding problem, however for this test data set I find that we can just use DFS - which is not strictly a Euler Path finding solution because the DFS solution here alone can’t decide if an edge we are going to remove is a ‘bridge edge’ (which, if removed will never makes us traverse back to the graph). I think the solution here is not sound to cover any type of Euler Path, but is just lucky enough to pass the existing test data set.

#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>
#include <stack>

using namespace std;

const int LIMIT = 501;
int F;
vector<int> degree(LIMIT, 0);
vector<vector<int>> adj(LIMIT, vector<int>(LIMIT, 0));
stack<int> path;

void dfs(int idx) {
    if (!degree[idx]) {
        path.push(idx);
        return;
    }
    
    for (int i = 1; i < LIMIT; ++i) {
        if (adj[idx][i] <= 0) continue;
        --adj[idx][i]; --adj[i][idx]; --degree[idx]; --degree[i];
        dfs(i);
    }
    path.push(idx);
}

int main() {
    ifstream fin("fence.in");
    ofstream fout("fence.out");
    fin >> F;
    int v1, v2;
    for (int i = 0; i < F; ++i) {
        fin >> v1 >> v2;
        adj[v1][v2]++; adj[v2][v1]++;
        degree[v1]++; degree[v2]++;
    }
    int start = 1;
    for(int i = 1; i < LIMIT; ++i){
        if(degree[i] % 2){
            start = i;
            break;
        }
    }

    dfs(start);
    
    while (!path.empty()) {
        cout << path.top() << endl;
        fout << path.top() << endl;
        path.pop();
    }
}