## 11175 - From D to E and Back

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
black.phoenix wrote:
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
New poster
Posts: 34
Joined: Mon Nov 17, 2003 10:41 am
sclo wrote:
black.phoenix wrote:
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.)
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Could someone give me more test input /output?
I got WA all the time.