AtomRush's blog

Tanya and Password 288 DIV2 D
By AtomRush, 9 years ago, In English

I am trying to solve this I learned about euler path . I understood how we make a edge between s[0]s[1]->s[1]s[2] and we have calculated whether a euler path exist or not . if it exist we did dfs i can't understand this type of dfs . if somebody can help me solving this somebody's accepted code

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This dfs is used to find the topological order of a graph, try reading about it, so what he is doing is find the beginning vertex b and he runs a topological order from b, which is stored in ans (as you will learn it is stored in reverse order and that is why he reverse the content), once the topological order is done, traverse it and check if everything goes right, I mean the graph becomes a chain, then output it. I don't know if this is an eulerian path algorithm, but in this case it works because if there is a solution it must be a chain.

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

    Yes you are right .I just learned what topological sort is. Topological sort can be done only in DAG (Directed acyclic graph) Topological sort is basically arranging the vertices in a order such that if there is a edge from u->v then u should come before v in the sort . I mistook it for euler path .Can somebody provide me with a code yo understand euler path

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

      Actually, to find Euler Path, start from any vertex that has out-degree larger than in-degree and, if there's no such vertex, start from a random one. Then the pseudo-code would look as follows...

      find(v)
{
    for(every neighbour u of v)
    {
        delete edge v->u
        find(u)
    }
    
    append v to the path
}

      That algorithm will return the reverse Euler Path, so you'll need to print it backwards.

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

        Deletion is very important. Simply turning off the edge doesn't work if you end up iterating over it later, because that causes a TLE. I learnt that the hard way :( .

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

          Reverse happened with me . Turning off the edge gave me AC while deleting the edge gave me tle :(

          → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Euler paths exist in cyclic graphs too, in which a topological sort is not possible.

    Consider a graph with 3 vertices and 4 edges 1->2, 2->3, 3->1 and 1->2. Clearly it's not possible to topologically sort the vertices, but if we traverse the edges in that very same order, we have an Euler Path/Trail.

    As a matter of fact, unless the graph is a chain, if there's an Euler Path, then the graph has at least one cycle.

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

      @tenshi_kanade thank you. you explained it so neatly :D

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

You can solve this by using Hierholzer's algorithm without using dfs (I have solved this by this way).

This's Hierholzer's algorithm (from wiki):

Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.

As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.

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

    I read that algorithm when I was implementing my solution, and it talked about doubly linked lists, which seemed overly complicated to me. Then I went to the USACO pages to read the tutorial on Euler Tours again and I implemented the algorithm presented there.

    But now, after coding the recursive variant, I realize that (correct me if I'm wrong) Hierholzer's algorithm is actually the same as the DFS version they explain at USACO, only that the USACO version is recursive instead of iterative. With the DFS version, you go deeper and deeper until you reach a vertex with no out-going edges, then the algorithm goes back on the recursion stack until it finds a vertex with remaining out-going edges, then goes deep again until it gets stuck, then returns to some previous node, etc.. Additionally, the function adds a node to the path only when it has no remaining out-going edges, so if it gets stuck at a certain vertex v, it will first add all vertices that come after v in the recursion, then v, and then all the vertices that came before v. If you think about that, you'll see that it's actually joining different sub-tours, with v in the middle, just like Wikipedia's Hierholzer's implementation.

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

      Can you give me this tutorial's link, this seem very interesting. I ever know this recursion version.

      Because I don't know how to find the Euler path so I come to Google and I found Hierholzer's algorithm on wiki, this help me solve this problem :D

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

        Yes, of course. The USACO site seems to be down now, but here's the same text: Eulerian Tours Tutorial

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

          The code I posted above does the exact same thing of erasing a edge in dfs (not actually) How? consider a graph with vertices 1->2 1->3 1->5 2->3 . lets say I start my dfs from 1 . My graph[1].size is currently =3{2,3,5} my p[1] is set to 0 . While(p[v]<graph[v].size()) p[v]=0 graph[v].size() =3 so this is true it now increments p[v] by 1 and starts a dfs from 2nd vertice and this goes on till once p[v] equals 3 and it gets out so basically once a edge was used a dfs began p[v] was incremented and if ever it came back p[v] value is greater than graph[v].size() so it wont start a dfs thus erasing the edge and correct me if i am wrong to check if graph is connected i can do this i=1 to MAX_NODE if graph[i].size() !=p[i] // not connected

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

            Yes, exactly. If you increment a variable to know what edge you have to use next, it's basically the same as deleting the edges once you've used them.

            And indeed, if you only start the DFS from one node, then checking if graph[i].size() == p[i] for all i will be enough to know if there's an Euler Path or not.

            → Reply