10735  Euler Circuit
Moderator: Board moderators
10735  Euler Circuit
We need a hint for this problem.
Thanks in advance.
Thanks in advance.
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.
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?
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?
Hi!
my solution was similar :
 find maximal matching beetween points ( we are trying to match points that have indegoutdeg > 0 with points that have indegoutdeg < 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 ?
my solution was similar :
 find maximal matching beetween points ( we are trying to match points that have indegoutdeg > 0 with points that have indegoutdeg < 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 ?
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
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
Last edited by Cosmin.ro on Fri Oct 15, 2004 8:15 pm, edited 1 time in total.
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.
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.
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 ).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.
After making this modification i got AC

 Experienced poster
 Posts: 123
 Joined: Thu Feb 10, 2005 4:46 am
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 flowcircuit 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() )
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() )

 New poster
 Posts: 7
 Joined: Sat Jul 09, 2005 7:58 pm
10735 WA
getting WA
I have tried my program with the following IO
Input:
I have tried my program with the following IO
Input:
Output: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
anyone got AC plz give me some more IO1 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
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

 New poster
 Posts: 7
 Joined: Sat Jul 09, 2005 7:58 pm
thanks mf for your reply
I was mistaken. Now i have fixed it.
For that input now my program gives
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
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
Last edited by Ahmed_Hasan on Fri Jan 13, 2006 4:45 pm, edited 1 time in total.
This doesn't always work. For example, consider the following graph. If you start by removing the cycle 1321, you won't find eulerian circuit.Ahmed_Hasan wrote: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.
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)

 New poster
 Posts: 7
 Joined: Sat Jul 09, 2005 7:58 pm