Блог пользователя Danish_amin_01

Help needed in CSES Graph Problem-Mail Delivery.
Автор Danish_amin_01, история, 4 года назад, По-английски

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 :)

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      8 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 << ' ';
}
      → Ответить