这道题貌似有那么一点复杂，看某大佬的博客，仿佛涉及了很多高端知识，还有一个二分图的性质… 我们判定奇圈，可以利用二分图的性质实现
对于这样一张图，假如所有黑色的部分为一个偶圈，也就是说他是一个二分图，交替染色不冲突，假设有虚线的这样一条线，那么B部分为奇圈，自然原图斩去B部分的边数为偶数，那么绿色框住的地方就应该是一个奇圈，然而奇圈的话，染色又会出现毛病，而之前又没有出现毛病，所以如果是二分图的话就一定不行，所以我们就判边连通分量是否是二分图就可以了，可能您没看懂我在说什么…我也没懂我在说什么… 反正二分图就是不行..因为染色不冲突，所以为偶圈，所以不行，因为题目必须要求奇数个骑士…
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define MAXN 1004 #define MAXM 1001000 int n,m,top,tail=1,timer,final; int head[MAXN],dfn[MAXN],low[MAXN],col[MAXN],mark[MAXN],stk[MAXM],fuck[MAXN]; int G[MAXN][MAXN]; struct Line{ int from,to,nxt,vis; }line[2*MAXM]; void add_line(int from,int to){ tail++; line[tail].from=from; line[tail].to=to; line[tail].nxt=head[from]; head[from]=tail; line[tail].vis=0; } bool judge(int u){ for(register int i=head[u];i;i=line[i].nxt){ int v=line[i].to; if(mark[v]){ if(col[v]==-1){ col[v]=!col[u]; return judge(v); } else if(col[v]==col[u]) return true; } } return false; } void getcolor(int u){ memset(mark,0,sizeof(mark)); int now; do{ now=stk[top--]; mark[line[now].from]=true; mark[line[now].to]=true; }while(line[now].from!=u); memset(col,-1,sizeof(col)); col[u]=0; if(judge(u)) for(register int i=1;i<=n;i++) if(mark[i]) fuck[i]=true; } void tarjan(int u){ dfn[u]=low[u]=++timer; for(register int i=head[u];i;i=line[i].nxt){ int v=line[i].to; if(line[i].vis)continue; line[i].vis=line[i^1].vis=true; stk[++top]=i; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]) getcolor(u); }else{ low[u]=min(low[u],dfn[v]); } } } void init(){ tail=1;top=0;timer=0;final=0; memset(G,0,sizeof(G)); memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(stk,0,sizeof(stk)); memset(fuck,0,sizeof(fuck)); } int main(){ while(scanf("%d%d",&n,&m),n||m){ init(); for(register int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); G[u][v]=G[v][u]=true; } for(register int i=1;i<=n;i++){ for(register int j=i+1;j<=n;j++){ if(!G[i][j]){ add_line(i,j); add_line(j,i); } } } for(register int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(register int i=1;i<=n;i++) if(!fuck[i]) final++; printf("%d\n",final); } return 0; }