kittyK's blog

A directed graph is given and you have to output one of the odd cycles
By kittyK, history, 4 years ago, In English

Given a graph with n nodes and m edges . n ≤ 100,000 and m ≤ 1,000,000 . We have to find any odd cycle.

Question Link

How to solve this problem ? I tried in naive way. I just stored the nodes when I get any cycle of odd length . But it will obviously TLE.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Check whether the Graph is Bipartite. A graph with an odd cycle can never be bipartite.

You can do this by running a BFS and coloring the odd and even levels with two colors. If you find any adjacent nodes with the same color, this means they are starting and endpoints of the odd cycle. Run another BFS/DFS to find the odd cycle.

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

    The graph is directed; it's not exactly clear what bipartite means on directed graphs.

    And the BFS method no longer works, either. Consider the graph with edges 1->2, 1->3, 2->3, and doing a BFS from vertex 1. vertex 2 (odd distance) is adjacent to vertex 3 (odd distance), but this is not a cycle.

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

      can you check my code ? any other way to optimize it ?

      I searched for a cycle in directed graph and when I found one, I checked whether it is a odd cycle or not. If it is a odd cycle then I found the cycle using the parent information. verdict is TLE

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

        There are two things that matter for an algorithm: correctness and efficiency.

        You shouldn't be thinking about optimizations at the code level unless you are convinced your algorithm is both correct and efficient.

        Before thinking about efficiency, you should be thinking about correctness (and you should be trying to judge these things before you submit and get a verdict, so I'm going to ignore your TLE verdict for now). You can often optimize a correct but inefficient algorithm to make it more efficient, but usually if you have an efficient but incorrect algorithm it's just the wrong idea altogether. So, why does your algorithm work? From your description, it sounds like you've just looked for a single cycle and then exited once you've found it. What happens if the cycle you found is even length? Do you just keep going, or do you declare that there is no odd cycle?

        If you keep going and looking for odd cycles, how long does your program take? Do you just do a single DFS through the graph? Is this guaranteed to find an odd cycle if there is one? Why?

        These are the questions you should be asking before you even sit down and code your algorithm, let alone optimize the code.

        I will say that I don't know the solution to the problem and I haven't thought about it too long. My guess is that it's probably relatively difficult if no one has given a correct solution in the comments yet, but I don't know. Perhaps you can do something with the DFS tree but it's not clear to me.

        → Reply