Блог пользователя aka.Sohieb

Автор aka.Sohieb, история, 8 лет назад, По-английски

Hello,

How to solve problem Odd Cycle from ACM-ICPC Asia — Daejeon regional contest.

The statement briefly:

Given simple directed graph having no self-loops or multiple edges, detect if it has any directed odd cycle (cycle with odd length) and if yes print description of an arbitrary odd cycle of the input graph.

The graph has n nodes ( n <= 100000 ) , m edges ( m <= 1000000).

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Consider some cycle, not necessarily odd A1, A2, ..., Ak=A1. Let's color each vertex from the cycle in black or white so that adjacent nodes in the cycle have different colors. It's easy to see that this is possible if and only if the cycle is of even length.

From the written above we can easily use DFS to simulate the process efficiently. We will consider every strongly connected component of the graph separately, because there can't be a cycle containing nodes from two different strongly connected components (also this allows us to arbitrarily choose the initial node for the DFS explained below). Take an arbitrary vertex, color it white and run a depth-first search from it. At any moment, say we are calling DFS from V and now we are at some of its children, say U. If U is used, then if the colors of U and V are the same, then here is an odd cycle (it should be easy for you to restore the cycle). If U is not used, then color it in V's opposite color and run DFS from it.

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

    I thought in something like that did not work.

    how would your algorithm deal with test case like this if the DFS takes this path 1-2-3-4-5-6-7-8

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

      Oh, sorry, I think we should check also the reversed edges to see if two adjacent vertices have the same color but we can continue the dfs only through regular edges. So if you are in vertex 7, you can go to 8 but should also check 6 and 3, not only 8 :)

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

        But that did not solve the problem yet or i misunderstand you,

        the solution to this case is the nodes ( 1-2-3-7-8 ), so please could you simulate how the DFS detect this cycle if it start from 1 and go from 3 to 4 before 7?!

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

          Ouch! I am extremely sorry for this, you are absolutely right! Next time I will try to get accepted before trying to help :(

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

P_Nyagolov has generally the right idea, but he's overcomplicating it a little (edit: I got AC now).

Duplicate all vertices of the graph in a new graph that has black and white vertices. Similarly, duplicate all edges so that if a->b is an edge in the original graph, then the new graph has two edges a black -> b white and a white -> b black.

Now odd cycles in the original graph are paths between v white and v black in the new graph. Therefore, there is an odd cycle that contains vertex v if and only if v white and v black are in the same SCC. If you find any vertex for which this is true, do a DFS from v white and record the path you take until reaching v black.

We have only one thing to take care of: the question asks for a simple cycle (no repeated vertices), and our formed cycle is not necessarily simple. So you should check if any node is repeated in the cycle you formed, and take only the part of the cycle between those repetitions if it happens (e.g. the cycle A B C D B F G A becomes B C D B, because B is the first repeated vertex). Due to the way we constructed our cycle, this is now guaranteed to be a simple odd cycle.

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

I color the nodes as P_Nyagolov said then search for an edge (u -> v) such that color[u] == color[v], I find any path of even length (BFS or DFS, visited[node][parity]) that goes from v to u and that path with the edge (u -> v) would form a cycle of odd length.

This cycle may not be simple, but it seams like the checker of the problem does not check if it's simple or not! I get RTE when I insert the cycle into a set and assert(set.size()==cycle.size()). I get Accepted without this assertion.

You can make the cycle simple by cutting out smaller cycles as ffao said, but be careful as you may cut a cycle of odd length and leave a cycle of even length! The path of even length may contain odd number of odd cycles and odd number of edges that don't belong to any cycle, or only even cycles and even number of edges that don't belong to any cycle. So once you found a cycle of odd length, cut it and print it. Otherwise, after removing all even cycles, the remaining nodes should form an odd cycle.

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

    lolwut it's true, I completely removed the part of the code that cuts cycles and still got AC. Why would they ask for something and then not check it at all? o_O