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. 

• 唉 看得我晕…… (0) alpc02 2006-08-09 22:28:57
  • 什么是2-connected components (0) zhao0057 2006-08-10 01:14:42
    • 就是不含割点的块 (0) xfxyjwf 2006-08-10 01:16:35
    • 删除任意一个点之后的剩余图 一定还是一个连通图 (0) sunmoonstar 2006-08-10 09:01:01
      • 从看到题到搞定它历经了四十多天，不容易…… (0) zhao0057 2006-09-27 20:05:24
        • Re:从看到题到搞定它历经了四十多天，不容易…… (25) IceKingdom 2009-03-10 12:09:10
          • 7个月，终于搞定……神啊……另：POJ AC 400 题留念 (85) IceKingdom 2009-05-21 00:33:27
• Re:Explanation & Gotchas (1242) tempfor 2007-08-31 17:20:31
  • Re:Explanation & Gotchas (14) tempfor 2007-08-31 17:21:28