Suggestions needed for improving eulerian path algorithm for CSES Mail Delivery problem

Question

I am getting time limit exceeded for my solution for CSES Mail Delivery for some test cases.

Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a route whose starting and ending point are the post office, and that goes through every street exactly once.

The problem essentially requires finding eulerian path.For algorithm I referred following description of Hierholzer’s algorithm : link

Following are some code snippets of my solution :

        LinkedList<Integer> adj[] = new LinkedList[n];

        ArrayDeque<Integer> s = new ArrayDeque<>();
        s.push(0);
        int curr_v = 0;
        int g[][] = new int[n][n];
        boolean flag = false;
        while (!s.isEmpty()) {

            flag = false;
            while(adj[curr_v].size() > 0) {
                //System.out.println(curr_v);
                int next_v = adj[curr_v].remove();
                if(g[curr_v][next_v] == 1){
                    continue;
                }
                flag = true;
                s.push(curr_v);
                g[curr_v][next_v] = 1;
                g[next_v][curr_v] = 1;
                curr_v = next_v;
            }
            if(!flag){
                circuit.add(curr_v + 1);
                curr_v = s.pop();
            }
        }

Full code can be found at My submission link

Can someone please suggest me how I can improve above code to pass all tests

Answer 1

The very first theorem of graph theory was presented in 1735 by Leonhard Euler.

The problem was known as the Seven Bridges of Königsberg.[80] The city of Königsberg, Prussia was set on the Pregel River, and included two large islands that were connected to each other and the mainland by seven bridges. The problem is to decide whether it is possible to follow a path that crosses each bridge exactly once and returns to the starting point. It is not possible: there is no Eulerian circuit.

In modern graph theory terms the trick is to determine if every node has the same in-degree as its out-degree. If they are equal, then every time the path reaches a node there must be an unused edge available to leave it.

Euler's insight allows an algorithm to be designed to find the Euler circuit, if it exists, that is almost trivial

Algorithm:

ASSERT graph directed
ASSERT in-degree == out-degree for all vertices
SET vertex to first
WHILE true
    ADD vertex to circuit  
    FIND next vertex along unused edge
    MARK edge used
    IF no unused edge
        STOP

C++ method signature

    /// @brief  Find euler path through graph
    /// @param g graph
    /// @return vector of vertex indices on path
    /// If no euler path, exception thrown
    
    std::vector<int> euler( const cGraph& g);

Unit test:

TEST(Euler2)
{
    raven::graph::cGraph g;
    g.directed();
    g.findorAdd("0","1");
    g.findorAdd("0","6");
    g.findorAdd("1","2");
    g.findorAdd("2","0");
    g.findorAdd("2","3");
    g.findorAdd("3","4");
    g.findorAdd("4","2");
    g.findorAdd("4","5");
    g.findorAdd("5","0");
    g.findorAdd("6","4");

    auto act = euler(g);

    CHECK_EQUAL(8, act.size());

    std::vector<std::string> exp1 { "0", "1", "2", "0", "6", "4", "2", "3", "4", "5", "0" };

    auto sact = g.userName( act );

    CHECK(std::equal(
            exp1.begin(),
            exp1.end(),
            sact.begin()));
}

C++ implementation:

   std::vector<int> euler(const cGraph &g)
        {
            // firewall
            if (!g.isDirected())
                throw std::runtime_error(
                    "euler:  needs directed graph ( 2nd input line must be 'g')");
            for (int vi = 0; vi < g.vertexCount(); vi++)
                if (g.adjacentIn(vi).size() != g.adjacentOut(vi).size())
                    throw std::runtime_error(
                        "euler: every vertex in-degree must equal out-degree");

            // working copy of graph
            cGraph work = g;

            // list to store circuit
            std::vector<int> circuit;

            // start at first vertex
            int curr_v = 0;

            while (1)
            {
                // add vertex to circuit
                 circuit.push_back(curr_v);

                // find next vertex along unused edge
                auto vadj = work.adjacentOut(curr_v);
                if (!vadj.size())
                    break;
                int next_v = vadj[0];

                // remove used edge
                work.remove(work.find(curr_v, next_v));

                // continue from new vertex
                curr_v = next_v;
            }

            return circuit;
        }

Complete application code:

https://github.com/JamesBremner/PathFinder

Code to generate random Euler graphs of specified node count:

void genEuler(const std::vector<std::string> &q)
{
    int vmax = atoi(q[1].c_str());
    theGraph.clear();
    theGraph.directed();
    for (int k = 0; k < vmax; k++)
    {
        theGraph.add("V" + std::to_string(k));
    }    
    int v1 = 0;
    for( int k = 0; k < vmax; k++ )
    {
        int v2 = v1;
        while( v2 == v1)
            v2 = rand() % vmax;
        theGraph.addEdge(v1,v2);
        v1 = v2;
    }
    theGraph.addEdge(v1,0);
}

Performance Results:

Node Count	Run Time ( secs )
1,000	0.02
10,000	2.0
100,000	125.0