11175 - From D to E and Back

black.phoenix · Post by **black.phoenix** » Tue Feb 27, 2007 1:50 pm

Hello!!!

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

Thanks!!!

rio · Post by **rio** » Tue Feb 27, 2007 4:10 pm

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 · Post by **sclo** » Tue Feb 27, 2007 9:24 pm

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 · Post by **black.phoenix** » Wed Feb 28, 2007 8:58 pm

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!!!

Observer · Post by **Observer** » Thu Mar 01, 2007 5:30 am

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?

black.phoenix · Post by **black.phoenix** » Thu Mar 01, 2007 4:49 pm

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"

Observer · Post by **Observer** » Thu Mar 01, 2007 5:28 pm

But doesn't we require D to be a directed graph? I think that means all edges in D should be directed edges.

Darko · Post by **Darko** » Thu Mar 01, 2007 6:06 pm

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 · Post by **black.phoenix** » Thu Mar 01, 2007 8:47 pm

I still don't understand this problem....

sclo · Post by **sclo** » Fri Mar 02, 2007 12:03 am

SPOILER:

DELETED

Ivan · Post by **Ivan** » Fri Mar 02, 2007 4:55 pm

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 · Post by **Abednego** » Fri Mar 02, 2007 7:20 pm

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?

Ivan · Post by **Ivan** » Fri Mar 02, 2007 9:34 pm

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 · Post by **Abednego** » Fri Mar 02, 2007 9:49 pm

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.

black.phoenix · Post by **black.phoenix** » Sat Mar 03, 2007 1:04 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!!!