题解 SP2878 【KNIGHTS - Knights of the Round Table】

· · 题解

提供一篇有严谨结论证明的题解。

本题最关键的结论是：点双连通图中若包含一个奇环，则所有点都在至少一个简单奇环上。

先在图中选出最初的奇环，此时一定满足两个条件：

1.所有点都在至少一个简单奇环上；

2.任意点对 u,v 间存在长为奇数的路径和长为偶数的路径。

重复以下操作：

在原图中去掉选出的所有点，原图分为若干连通块。对于任意连通块 X 一定和已选出的至少两个点 u,v 相连（若只与一个点相连，则这个点是割点，与点双矛盾）。

选出 u-X-v 的任意一条路径（因为 X 连通所以这样的路径一定存在）。若这条路径长为奇数，和 u,v 间长为偶数的路径可以拼成奇环，否则和 u,v 间长为奇数的路径可以拼成奇环。

对于路径上两点 x,y，x-u-v-y 可以是长为奇数的路径和长为偶数的路径。对于路径上一点 x 和之前已经选出的一点 a，x-u-a 可以是长为奇数的路径和长为偶数的路径。因此两个条件依然满足。

重复以上操作直到所有点都被选出，结论得证。

有了结论以后本题就很简单了，先建补图，补图上 Tarjan 求点双，对于每一个点双二分图染色判断是否有奇环，不在任何一个有奇环的点双上的点都无法参加会议。

#include<bits/stdc++.h>
using namespace std;
const int N=1003;
bool e[N][N],b[N],f[N],o;
int r,n,dfn[N],low[N],st[N],tp,id,ct,cl[N];
basic_string<int>dcc[N];
void tar(int x){//Tarjan求点双
    dfn[x]=low[x]=++id,st[++tp]=x;
    for(int i=1;i<=n;++i)if(e[x][i]){
        if(!dfn[i]){
            tar(i),low[x]=min(low[x],low[i]);
            if(low[i]>=dfn[x])for(dcc[++ct].clear(),dcc[ct]+=x;dcc[ct]+=st[tp],st[tp--]!=i;);
        }else low[x]=min(low[x],dfn[i]);
    }
}
void dfs(int x){//二分图染色
    for(int i=1;i<=n;++i)if(e[x][i]&&b[i]){
        if(cl[i]==2)cl[i]=!cl[x],dfs(i);
        else if(cl[i]==cl[x])o=1;
    }
}
int main(){
    int m,i,j;
    while(scanf("%d%d",&n,&m),n){
        memset(dfn+1,0,n*4),memset(f+1,1,n),id=ct=tp=0;
        for(i=1;i<=n;++i)memset(e[i]+1,1,n),e[i][i]=0;
        while(m--)scanf("%d%d",&i,&j),e[i][j]=e[j][i]=0;//建补图
        for(r=1;r<=n;++r)if(!dfn[r])tar(r);
        for(i=1;i<=ct;++i){
            for(int j:dcc[i])b[j]=1,cl[j]=2;
            o=cl[j=dcc[i][0]]=0,dfs(j);
            for(int j:dcc[i])if(b[j]=0,o)f[j]=0;
        }
        for(i=1,j=0;i<=n;++i)j+=f[i];
        printf("%d\n",j);
    }
    return 0;
}