### 11175 - From D to E and Back

Posted:

**Tue Feb 27, 2007 1:50 pm**Hello!!!

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

Thanks!!!

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

Thanks!!!

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=37&t=15046

Page **1** of **2**

Posted: **Tue Feb 27, 2007 1:50 pm**

Hello!!!

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

Thanks!!!

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

Thanks!!!

Posted: **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

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

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

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

Posted: **Thu Mar 01, 2007 5:30 am**

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.

Posted: **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"

Posted: **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.

Posted: **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)?

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

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

Posted: **Fri Mar 02, 2007 12:03 am**

SPOILER:

DELETED

DELETED

Posted: **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.

I managed to accept a code which is obviously wrong on pretty simple

test cases.

Posted: **Fri Mar 02, 2007 7:20 pm**

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.

Posted: **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...

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

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

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

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