11175  From D to E and Back
Moderator: Board moderators

 New poster
 Posts: 8
 Joined: Sun Aug 06, 2006 3:07 am
11175  From D to E and Back
Hello!!!
What Graph Theory must be used to solve this problem???
Thanks!!!
What Graph Theory must be used to solve this problem???
Thanks!!!
You do not know whether the path is easy or hard unless you walk through it.

 New poster
 Posts: 8
 Joined: Sun Aug 06, 2006 3:07 am
Sorry.... I didn't get the idea yet... could you give me some more hints???
Maybe I'm thinking about the problem in a wrong way.... take 3rd case:
4
3
0 1
2 1
2 3
Now draw a directed graph where it has nodes namely 0, 1, 2, 3 and making edges as arrows from 0 to 1, from 2 to 1 and from 2 to 3. This graph can be the lying graph from the undirected (or directed both ways) graph with nodes n0,n1,n2,n3,n4 where there's an edge called A between each nA,nA+1 and between the others vertices there's no edge.
I was thinking in this way, so for the 3rd case I thought the answer would be "Yes" as it's possible for E to be the lying graph of D the way I described above. But I'm wrong and I'd like to know the correct logic to solve this problem.
Waiting for you replies!!!
Maybe I'm thinking about the problem in a wrong way.... take 3rd case:
4
3
0 1
2 1
2 3
Now draw a directed graph where it has nodes namely 0, 1, 2, 3 and making edges as arrows from 0 to 1, from 2 to 1 and from 2 to 3. This graph can be the lying graph from the undirected (or directed both ways) graph with nodes n0,n1,n2,n3,n4 where there's an edge called A between each nA,nA+1 and between the others vertices there's no edge.
I was thinking in this way, so for the 3rd case I thought the answer would be "Yes" as it's possible for E to be the lying graph of D the way I described above. But I'm wrong and I'd like to know the correct logic to solve this problem.
Waiting for you replies!!!
You do not know whether the path is easy or hard unless you walk through it.
How many directed edges does your graph D have?black.phoenix wrote:Now draw a directed graph where it has nodes namely 0, 1, 2, 3 and making edges as arrows from 0 to 1, from 2 to 1 and from 2 to 3. This graph can be the lying graph from the undirected (or directed both ways) graph with nodes n0,n1,n2,n3,n4 where there's an edge called A between each nA,nA+1 and between the others vertices there's no edge.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 New poster
 Posts: 8
 Joined: Sun Aug 06, 2006 3:07 am
none... the graph is undirected (or directed both ways as I said)..... it's a simple graph with 5 vertices which contains four edges.... from v0 to v1 (edge0), from v1 to v2 (edge1), from v2 to v3 (edge2), from v3 to v4 (edge3).... from this graph I can draw E, following the logic from the problem statement, which gives the lying graph for the 3rd example..... but the answer is "No"
You do not know whether the path is easy or hard unless you walk through it.
But doesn't we require D to be a directed graph? I think that means all edges in D should be directed edges.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
In other words  if you treat those undirected edges as two directed ones, and then you follow the instructions from the problem statement, how many nodes will the lying graph have?
I guess I am overthinking this one  can this be solved by calculating the square root of the matrix (or  determining if one exists)?
I guess I am overthinking this one  can this be solved by calculating the square root of the matrix (or  determining if one exists)?

 New poster
 Posts: 8
 Joined: Sun Aug 06, 2006 3:07 am
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Can you show me one of those simple test cases? Perhaps you are not using the fact that D is allowed to have selfloops and multiple edges?Ivan wrote:The input data seem to be a bit weak.
I managed to accept a code which is obviously wrong on pretty simple
test cases.
If only I had as much free time as I did in college...

 New poster
 Posts: 8
 Joined: Sun Aug 06, 2006 3:07 am
Hello Abednego!!!
Could you give me a more detailed explanation on how to solve this problem??? I've read what sclo wrote but I didn't get the idea yet.
He treated a vertex in D as a pair (a,b) where a and b are its edges. But why if there's some directed edge from (a,b) to (c,d) in D guarantees that b=c is in D???
I'd like to know if you could also point out what I misunderstood about the problem from my last posts above.
Thanks!!!
Could you give me a more detailed explanation on how to solve this problem??? I've read what sclo wrote but I didn't get the idea yet.
He treated a vertex in D as a pair (a,b) where a and b are its edges. But why if there's some directed edge from (a,b) to (c,d) in D guarantees that b=c is in D???
I'd like to know if you could also point out what I misunderstood about the problem from my last posts above.
Thanks!!!
You do not know whether the path is easy or hard unless you walk through it.