Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Danish_amin_01's blog

Help needed in CSES Graph Problem-Mail Delivery.
By Danish_amin_01, history, 4 years ago, In English

Problem Link.
I am facing Time Limit Exceed in this problem and I am not able to improve my code any further.
(The following code is in python, but I have even tried in same thing in C++ and got TLE for last test case.)

My Code

I have implemented the method from this Link of CP-Algorithms in my code.
Please read my code. I have mentioned what could be the bottleneck in my code, and I don't know how to overcome this problem. If I avoid removing edges from graph, then how should I track what edges not to visit.
Thanks in advance and If you want to help and don't understand what my problem is or anything else just comment for the same I would try to explain better what is my issue here.
Also you can simply comment some links or similar problems related to this so that I can do some further research.
Any kind of help is acceptable :)

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Change graph to set and it will probably pass. I have solved it using set.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks a lot buddy, I don't know why it didn't strike me to use sets. Anyways I am attaching my accepted code for those people who may stumble here in future for the same problem.

    AC-code

    I recommend to try with sets if not considered, before looking at code.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can u not use dfs to find euler path in an undirected graph? If so, can u pls share the code with me?

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Pasting a simple CPP implementation for any future reader. Using sets really eased the implementation.

      #include <iostream>
#include <vector>
#include <set>
using namespace std;

int m, n;
vector<int> res;
vector<set<int>> adj;

// euler circuit
void dfs(int curr)
{
    auto &edges = adj[curr]; 
    while(!edges.empty())
    {
        auto edge = *edges.begin();
        edges.erase(edge);
        adj[edge].erase(curr);
        dfs(edge);
    }
    res.push_back(curr);
}

int main()
{
    cin >> n >> m;
    adj.resize(n + 1);
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;
        adj[x].insert(y);
        adj[y].insert(x);  
    }
    
    for (int i = 1; i <= n; ++i)
    {
        if (adj[i].size() % 2)
        {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }

    dfs(1);
    
    if (res.size() != m + 1)
    {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    
    for (auto &r : res)
        cout << r << ' ';
}
      → Reply