Danish_amin_01's blog

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

| 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.

  • »
    »
    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.

    • »
      »
      »
      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?

    • »
      »
      »
      14 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 << ' ';
      }
      
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you tell why this is not working

        for(int neigh: set<int>(adjList[node])){ // copy the set since you are erasing after
                    adjList[node].erase(neigh);
                    adjList[neigh].erase(node);
                    dfs(neigh);
                }