ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1320. Graph Decomposition

AC in 0.031sec and 385k......but I need some help!
Posted by Yu YuanMing 25 Sep 2004 22:31
  It looks like a match problem......but you can't solve it in this way......

  Actually,I don't really know why my program will work.Could someone who got AC tell me?Prove my algorithm is right or show it is wrong.
  contacts me: yym2008@hotmail.com

  By the way,I found some interesting.If you use "read" and "eof" you will WA on test6,but if you use "readln" or "seekeof" instead,you can pass it......
It's always possible to decompose a connected graph
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 12 Oct 2004 15:29
First draw a graph with two adjacent edges
Then add two edges (say x and y), wherever they are. Now find a path connecting these two edges. Say the path goes across the pairs (A1,A2), (B1,B2), (C1,C2), then you can re-combine the pairs, say (x,A1), (A2,B1), (B2,C1), (C2,y). This is always feasible.
Now, just count the number of edges in each component of the given graph. If one or more numbers is odd, the answer is 0, otherwise it's 1.