Mail Delivery

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.

Example:

Input: n = 6, m = 8, edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 6}, {3, 5}, {3, 6}, {4, 5}}
Output: 1 2 3 5 4 2 6 3 1 

Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> adj[100005];
int vis[200005];

void mailDelivery(int n, int m,
                  vector<vector<int>> &edges)
{

    for (int i = 0; i < m; i++)
    {
        int u = edges[i][0];
        int v = edges[i][1];

        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++)
    {
        if (adj[i].size() & 1)
        {
            cout << "IMPOSSIBLE";
            return;
        }
    }
    stack<int> st;
    st.push(1);
    vector<int> path;
    while (!st.empty())
    {
        int v = st.top();
        int f = 0;
        while (!adj[v].empty())
        {
            pair<int, int> p = adj[v].back();
            adj[v].pop_back();
            if (!vis[p.second])
            {
                st.push(p.first);
                vis[p.second] = 1;
                f = 1;
                break;
            }
        }
        if (!f)
        {
            path.push_back(v);
            st.pop();
        }
    }
    if (path.size() != m + 1)
    {
        cout << "IMPOSSIBLE";
        return;
    }
    for (int i : path)
        cout << i << " ";
}
int main()
{
    int n = 6, m = 8;

    vector<vector<int>> edges = {{1, 2},
                                 {1, 3},
                                 {2, 3},
                                 {2, 4},
                                 {2, 6},
                                 {3, 5},
                                 {3, 6},
                                 {4, 5}};

    mailDelivery(n, m, edges);

    return 0;
}