10735 - Euler Circuit

[BiK]

We need a hint for this problem.

Thanks in advance.

[miras]

Hay BiK...


i think you should try to combine sth. like indeg(k)=outgeg(k)+1 ,where k is the numer of node...

[Cosmin.ro]

indegree(i) == outdegree(i) so we know for each node i how many of the undirected edges must point out and how many must point in. We can find such an orientation using maxflow on a bipartite network wich has as nodes the unoriented edges of the original graph and the nodes of the original graph, and then all we are left to do is to find a euler circuit using the classical way.

[davidsu]

Hello Cosmin.ro, I used the same idea as yours, using max flow to assign undirected edges directions. But I get WA. I found though the new graph is indegree(i)==outdegree(i) and undirected edge degree(i) is even for vertex i, it still can't be solved by classical way.

Or maybe I was wrong with your max flow, should there be remainder undirected edges after the max flow? Or there are something need to modify in classical way?

[cyfra]

Hi!

my solution was similar :

- find maximal matching beetween points ( we are trying to match points that have indeg-outdeg > 0 with points that have indeg-outdeg < 0 )

thanks to this we can direct some undirected edges.

So now if for all verticles indeg(v)==outdeg(v) and degree(v) is even the eulear circuit should exist ...

But I still keep getting WA.

I think that my ideas are correct. Are they, or am I missing something ?

[windows2k]

Hello,
you say it is a classical problem.
But I didn't meet the problem yet.
Could you give some reference url or "key words" to me ?
Thx

[Cosmin.ro]

to cyfra: the graph may be disconnected so even if indeg_i == outdeg_i there is still no solution
to windows2k: finding a euler circuit or euler tour in a eulerian graph is a classic task, you can find it in most algorithm books, also USACO has a subsesction dedicated to it.

warning: I haven't solved the task yet

[davidsu]

Got someone's help and got accept.
When indeg(v)==outdeg(v) and degree(v) is even the euler circuit exist, but it can't be solved by choosing arbitrary edges like the classical ways.
The way I did is to assign those remainder undirected edges directions(after the max flow) until there are no undirected edges left by travelling only on undirected edge circuit first.

[tthoai]

Got someone's help and got accept.
When indeg(v)==outdeg(v) and degree(v) is even the euler circuit exist, but it can't be solved by choosing arbitrary edges like the classical ways.

I've just figured it out that a small modification in the classical algorithm would work with a graph that meets above condition ( indeg(v)==outdeg(v) and degree(v) is even ). What did I do is : in each recursive step I try to visit all undirected edges first and then all directed edges ( or the other way around ).

After making this modification i got AC

[Destination Goa]

There is another way dealing with remaining undirected edges. When we have ideg==odeg - we must build a circuit (in terms of flow) on these remaining undirected edges (provided 'udeg' is even, this will keep ideg==odeg when flow-circuit is constructed). Since this circuit (once built) can be freely flipped without affecting result existence, we just direct one of remaining undirected edges wherever we want, and then reballance ideg/odeg again until we blow off (ideg==odeg, deg - even) constraints on some step or eliminate any and all undirected edge(s). Then we may happily construct Euler cycle using classical algorithm.

P.S: The graph will always remain connected if ideg==odeg and underlying undirected graph is connected, so this shouldn't be checked (I've checked using abort() )

[Ahmed_Hasan]

getting WA
I have tried my program with the following IO

Input:

9

6 8
1 2 U
2 3 U
3 4 U
4 5 U
2 5 D
2 6 U
6 4 U
4 1 U

6 13
1 2 U
1 3 U
1 3 U
1 4 U
2 3 U
2 5 D
2 5 U
5 3 D
5 6 U
6 3 U
4 6 U
4 6 U
3 4 U


6 13
1 2 U
1 3 U
1 3 U
1 4 U
2 3 U
2 5 D
2 5 U
5 3 D
5 6 U
6 3 D
4 6 U
4 6 U
3 4 U

6 12
1 2 U
1 2 U
2 3 U
2 3 U
3 4 U
3 4 U
4 5 D
4 5 D
5 6 U
5 6 U
6 1 U
6 1 U

5 6
1 2 U
2 3 U
3 1 U
1 4 U
4 5 U
5 1 U


4 4
1 2 D
2 3 D
3 4 D
4 1 D

4 8
1 2 D
1 2 U
3 2 D
3 2 U
3 4 U
3 4 U
4 1 U
4 1 U

6 8
1 3 U
1 4 U
2 4 U
2 5 D
3 4 D
4 5 U
5 6 D
5 6 U

4 4
1 2 D
1 4 D
2 3 U
3 4 U

Output:

1 2 3 4 6 2 5 4 1

1 2 3 1 3 4 6 5 2 5 3 6 4 1

No euler circuit exist

1 2 3 4 5 6 1 2 3 4 5 6 1

1 2 3 1 4 5 1

1 2 3 4 1

No euler circuit exist

1 3 4 2 5 6 5 4 1

No euler circuit exist

anyone got AC plz give me some more IO

[mf]

For your input I get:

Code: Select all

1 2 5 4 3 2 6 4 1

1 3 1 2 5 3 2 5 6 4 3 6 4 1

1 2 5 3 2 5 6 3 1 4 6 4 3 1

1 2 3 4 5 6 1 2 3 4 5 6 1

1 2 3 1 4 5 1

1 2 3 4 1

1 2 3 4 3 2 1 4 1

1 3 4 2 5 6 5 4 1

No euler circuit exist

[Ahmed_Hasan]

thanks mf for your reply
I was mistaken. Now i have fixed it.
For that input now my program gives

Code: Select all

1 2 5 4 3 2 6 4 1 

1 2 5 3 1 3 2 5 6 3 4 6 4 1 

1 2 5 3 1 3 2 5 6 3 4 6 4 1 

1 2 3 4 5 6 1 2 3 4 5 6 1 

1 2 3 1 4 5 1 

1 2 3 4 1 

1 2 1 4 3 2 3 4 1 

1 3 4 2 5 6 5 4 1 

No euler circuit exist 

its almost like yours
but still i m getting WA


my idea is:

i pick a directed edge, find a cyclic path containing that edge. the path may contain directed or undirected edges. remove all edges of that path from the original graph. make all the undirected edges of that path directed so that the path remains cyclic. then i put all the edges of that path in a new graph(G). i repeat this process untill there is no directed edge in the orginal graph.

then i continue same process for the remaing undirected edges in the original graph.

then i print Euler ckt from the graph G

when i take an edge and if i fail to find a cycle then Euler ckt can't be made from the input graph.

logic:
let g1(v1,e1),g2(v2,e2),g3(v3,e3) are cyclic graphs where e1,e2,e3 are disjoint set that is e1,e2,e3 has no common element and let G(V,E) is any graph.
Now if (v1 union v2 union v3) == V
and e1 + e2 + e3 == E
then G is an Euler ckt

i m not sure about the logic. though i m getting WA may be the idea is wrong. if anybody can find that out plz tell me

[mf]

my idea is:

i pick a directed edge, find a cyclic path containing that edge. the path may contain directed or undirected edges. remove all edges of that path from the original graph. make all the undirected edges of that path directed so that the path remains cyclic. then i put all the edges of that path in a new graph(G). i repeat this process untill there is no directed edge in the orginal graph.

This doesn't always work. For example, consider the following graph. If you start by removing the cycle 1-3-2-1, you won't find eulerian circuit.

Code: Select all

5 7
1 3 U
3 2 D
1 2 U
2 4 U
4 1 D
2 5 U
5 1 D

(One of tours is: 1 3 2 4 1 2 5 1)

A better approach is to reduce this problem to bipartite matching. Check out http://acm.uva.es/board/viewtopic.php?t=6636 and http://algorithmist.com/index.php/UVa_10735

[Ahmed_Hasan]

Thanks mf. U helped a lot. Now I got it AC. I knew that there is a solution using max-flow in a bipartite graph, but i could not emagine the bipartite graph, i mean what the elements would be in the partitations of the bipartite graph, now i understand, thanks a lot.