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
-
- 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 self-loops 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.