11175 - From D to E and Back

[sclo]

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

The correct intepretation is: vertex in E is a pair (a,b), where a,b are vertex in D. If there exists vertices (a,b) and (c,d) in E and there is an edge from (a,b) to (c,d) in E, but b!=c in D, we have a contradiction.
Note this line:

There are no other edges in E.

I know I didn't say anything in much detail, or else I'll be spoiling it. What I said is already in the problem statement. Just think about how could we use that information, and when exactly do we output "No".

[LPH]

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

The correct intepretation is: vertex in E is a pair (a,b), where a,b are vertex in D. If there exists vertices (a,b) and (c,d) in E and there is an edge from (a,b) to (c,d) in E, but b!=c in D, we have a contradiction.

How would you sure that b!=c in D?
I think in this case we will know that b=c. For example:

Code: Select all

1
2
4
0 0
1 1
0 1
1 0

The answer is Yes. (A possible D is the graph that have only one vertex with two self edges.)
Reading edges top-down, we first know (from the first two edge of E) that in D, edge 0 point from some vertex X to itself and edge 1 point from some vertex Y to itself. (X and Y would be different if there are no more edge in E, so we should first assume that they are different.)
Then we read in 0->1, it means that for some vertex Z in D, edge 0 point to Z, edge 1 point from Z. So we know that Z=X (since the vertex edge 0 point to is vertex X) and Z=Y (since the vertex edge 1 point from is vertex Y), which means X=Y.
_____________________
BTW, my first ACC solution does wrong on this case.... (the last one is corrected.)

[windows2k]

Could someone give me more test input /output?
I got WA all the time.
Thx in advance.

[shihabrc]

can somebody plz post some i/o. already got several WA with this one.