Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:Explanation & Gotchas

Posted by tempfor at 2007-08-31 17:20:31 on Problem 2942
In Reply To:Explanation & Gotchas Posted by:biggates at 2006-08-09 20:01:04
> Summary :
> Given are N knights. Sometimes 2K+1 of them sit around a round table in such a way that no two neighbors hate each other. (Hate is symmetrical, if A hates B, then B hates A.) Output the number of knights that can never be a part of a such arrangement. 
> 
> Explanation :
> The first step is to understand the problem statement correctly. 
> 
> For example, consider 5 knights (A, B, C, D, E), where A hates D and E, B hates E, and C hates D. The only valid seating arrangement (up to symmetry) is A,B,C. Neither D nor E can ever sit at the round table, thus the answer is 2. 
> 
> The solution consists in taking the graph "which pairs may be neighbors", splitting it into 2-connected components and checking whether each component is bipartite. 
> 
> Proof: We want to find the set of vertices that lie on some odd cycle. Each odd cycle is completely contained in one of the 2-connected components. A graph contains an odd cycle iff it is not bipartite. It can be easily shown that IF (a graph is 2-connected) and (it contains an odd cycle) THEN each of its vertices lies on some odd cycle. 
> 
> Gotchas :
> A bridge is a special type of a 2-connected component, you probably want to handle it separately. 
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator