Page 2 of 2
Posted: Sat Mar 03, 2007 1:24 am
by sclo
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".
Posted: Mon Apr 30, 2007 5:21 pm
by LPH
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:
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.)
Posted: Sun May 06, 2007 7:54 am
by windows2k
Could someone give me more test input /output?
I got WA all the time.
Thx in advance.
Posted: Sat May 19, 2007 9:45 pm
by shihabrc
can somebody plz post some i/o. already got several WA with this one.