### doreshnikov's blog

By doreshnikov, 16 months ago, translation,

Hello everyone!

I thought that maybe someone on Codeforces can help me find an error or build a counterexample. If you remember matchings in non-bipartite graphs, then the problem with Kuhn's algorithm is as follows: we need to find an augmenting path, but we can arrive at the desired vertex via an edge of the wrong type, mark it as visited, and leave.

1. First attempt to solve the problem: do a dfs on vertices of the form (v, flag), where flag is the type of edge we arrived by. Obviously, this doesn't work: we can go through both (v, false) and (v, true) because they are different vertices, but then our augmenting path in the original graph is not simple, and we haven't actually found an augmenting path.

2. Second attempt to solve the problem: do the same thing as before, but explicitly forbid dfs to go to vertices that have already been visited (are on the path from the start to the current vertex), even if they were visited with a different flag. Something like this:

vis[v, flag] <- false for each v, flag
path = []

dfs(v, flag):
vis[v, flag] = true