## 11175 - From D to E and Back

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

Moderator: Board moderators

black.phoenix
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!!!
You do not know whether the path is easy or hard unless you walk through it.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
You don't need special theory.

Hint:
Let N1 be a set of nodes that has edge to 1. For example, if there are edges (0, 1), (1, 1), (5, 1), N1 sould be {0, 1, 5}. So as N2, and more..
Think about the relation between Ni and Nj

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
This problem is much easier IMO then the equivalent problem on undirected graphs. (Line graphs). I did use some datastructure to make it fasther though.

black.phoenix
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!!!
You do not know whether the path is easy or hard unless you walk through it.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
How many directed edges does your graph D have?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

black.phoenix
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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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)?

black.phoenix
New poster
Posts: 8
Joined: Sun Aug 06, 2006 3:07 am
I still don't understand this problem....
You do not know whether the path is easy or hard unless you walk through it.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
SPOILER:

DELETED
Last edited by sclo on Sat Mar 03, 2007 1:29 am, edited 1 time in total.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
The input data seem to be a bit weak.
I managed to accept a code which is obviously wrong on pretty simple
test cases.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
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?
If only I had as much free time as I did in college...

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria
I've got AC two programs - based on somewhat different logic.
For the case:
1
5
4
0 1
0 2
3 2
3 4
one outputs "yes", the other "no"...
Strange...

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
The answer should be No. Can you send me the one that says Yes? I'm curious to see how it managed to pass all the tests.
If only I had as much free time as I did in college...

black.phoenix
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!!!
You do not know whether the path is easy or hard unless you walk through it.