Page 1 of 2

11175 - From D to E and Back

Posted: Tue Feb 27, 2007 1:50 pm
by black.phoenix
Hello!!!

What Graph Theory must be used to solve this problem???

Thanks!!!

Posted: Tue Feb 27, 2007 4:10 pm
by rio
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

Posted: Tue Feb 27, 2007 9:24 pm
by sclo
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.

Posted: Wed Feb 28, 2007 8:58 pm
by black.phoenix
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!!! :-)

Posted: Thu Mar 01, 2007 5:30 am
by Observer
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?

Posted: Thu Mar 01, 2007 4:49 pm
by black.phoenix
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" :o

Posted: Thu Mar 01, 2007 5:28 pm
by Observer
But doesn't we require D to be a directed graph? I think that means all edges in D should be directed edges.

Posted: Thu Mar 01, 2007 6:06 pm
by Darko
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)?

Posted: Thu Mar 01, 2007 8:47 pm
by black.phoenix
I still don't understand this problem.... :cry:

Posted: Fri Mar 02, 2007 12:03 am
by sclo
SPOILER:



DELETED

Posted: Fri Mar 02, 2007 4:55 pm
by Ivan
The input data seem to be a bit weak.
I managed to accept a code which is obviously wrong on pretty simple
test cases.

Posted: Fri Mar 02, 2007 7:20 pm
by Abednego
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?

Posted: Fri Mar 02, 2007 9:34 pm
by Ivan
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...

Posted: Fri Mar 02, 2007 9:49 pm
by Abednego
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.

Posted: Sat Mar 03, 2007 1:04 am
by black.phoenix
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!!!