参考了Kuangbin巨的题解。
/* POJ 2942 Knights of the Round Table 亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突， 并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求： 1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置； 2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。 注意：1、所给出的憎恨关系一定是双向的，不存在单向憎恨关系。 2、由于是圆桌会议，则每个出席的骑士身边必定刚好有2个骑士。 即每个骑士的座位两边都必定各有一个骑士。 3、一个骑士无法开会，就是说至少有3个骑士才可能开会。 首先根据给出的互相憎恨的图中得到补图。 然后就相当于找出不能形成奇圈的点。 利用下面两个定理： （1）如果一个双连通分量内的某些顶点在一个奇圈中（即双连通分量含有奇圈）， 那么这个双连通分量的其他顶点也在某个奇圈中； （2）如果一个双连通分量含有奇圈，则他必定不是一个二分图。反过来也成立，这是一个充要条件。 所以本题的做法，就是对补图求点双连通分量。 然后对于求得的点双连通分量，使用染色法判断是不是二分图，不是二分图，这个双连通分量的点是可以 存在的 */
/*ID: onlyazh1LANG: C++TASK: Knights of the Round Table*/#include#include #include #include #include #include #include #include #include #include using namespace std;typedef unsigned long long ll;const int MAXN=1010;const int MAXM=1000010;int n,m,u,v,tot;int low[MAXN];int dfn[MAXN];int head[MAXN];int Stack[MAXN];int tmp[MAXN];int color[MAXN];bool ok[MAXN];bool can[MAXN];bool instack[MAXN];bool G[MAXN][MAXN];int idx,top,cc;struct Edge{ int v,nex;}edge[MAXM<<1];void addedge(int u,int v){ edge[tot].v=v; edge[tot].nex=head[u]; head[u]=tot++;}bool dfs(int u,int col){ color[u]=col; for(int i=head[u];i!=-1;i=edge[i].nex){ int v=edge[i].v; if(!ok[v]) continue; if(color[v]!=-1){ if(color[v]==col) return false; continue; } if(!dfs(v,!col)) return false; } return true;}void Tarjan(int u,int pre){ low[u]=dfn[u]=++idx; Stack[top++]=u; instack[u]=true; for(int i=head[u];i!=-1;i=edge[i].nex){ int v=edge[i].v; if(v==pre) continue; if(!dfn[v]){ Tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]){ int vn,cc=0; memset(ok,false,sizeof(ok)); do{ vn=Stack[--top]; ok[vn]=true; tmp[cc++]=vn; instack[vn]=false; }while(vn!=v); ok[u]=true; memset(color,-1,sizeof(color)); if(!dfs(u,0)){ can[u]=true; while(cc--) can[tmp[cc]]=true; } } } else if(instack[v]) low[u]=min(low[u],dfn[v]); }}void init(){ tot=top=idx=0; memset(G,false,sizeof(G)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(can,false,sizeof(can)); memset(head,-1,sizeof(head)); memset(instack,false,sizeof(instack));}int main(){ ifstream cin("in.txt"); while(cin>>n>>m&&n+m){ init(); while(m--){ cin>>u>>v; G[u][v]=G[v][u]=true; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&!G[i][j]) addedge(i,j); for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i,i); cout<<"***"<