OJ Board

Hello!!!

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

Thanks!!!

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

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.

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

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?

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"

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

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 still don't understand this problem....

SPOILER:



DELETED

The input data seem to be a bit weak.
I managed to accept a code which is obviously wrong on pretty simple
test cases.

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?

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

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.

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