10735 - Euler Circuit

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

10735 - Euler Circuit

Post by BiK »

We need a hint for this problem.

Thanks in advance.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras »

Hay BiK...


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

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by 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
New poster
Posts: 3
Joined: Fri Jan 31, 2003 10:02 am

Post by 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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by 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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by 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 :D

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by 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
Last edited by Cosmin.ro on Fri Oct 15, 2004 8:15 pm, edited 1 time in total.

davidsu
New poster
Posts: 3
Joined: Fri Jan 31, 2003 10:02 am

Post by 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
New poster
Posts: 2
Joined: Sat Oct 30, 2004 8:38 am

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

Post by 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
New poster
Posts: 7
Joined: Sat Jul 09, 2005 7:58 pm

10735 WA

Post by 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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by 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
New poster
Posts: 7
Joined: Sat Jul 09, 2005 7:58 pm

Post by 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
Last edited by Ahmed_Hasan on Fri Jan 13, 2006 4:45 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

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.
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
New poster
Posts: 7
Joined: Sat Jul 09, 2005 7:58 pm

Post by 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.

Post Reply

Return to “Volume 107 (10700-10799)”