spoj KNIGHTS - Knights of the Round Table 题解

· · 题解

昨天看到奇数个相邻点没边的环这玩意感觉很奇怪，怎么想都没有思路。今天再一看就茅塞顿开了——建反图之后一个奇环就对应一种方案。所以 n\leq 1000 的数据范围不是给的玩的。

我们知道如何判断一个图是否存在奇环——二分图染色即可。但是如何判断是否存在包含指定点的奇环呢？

首先一个点在至少一个简单环上当且仅当它所在点双大小 \geq 3。所以这个问题应该不弱于点双。先求出所有点双看看。

那么一个环肯定是在某个点双内部，不可能跨点双。如果一个点双通过了二分图测试，那肯定萎了；否则至少有一个奇环。奇环这东西很有趣，把它劈成两半一定变成一奇一偶；而且与之有一段公共部分的环上也一定所有点都在奇环上——如果新环是奇环那确实了，否则可以把公共部分换成原公共部分相对奇环的补集。

那很自然地引出一个猜想：如果一个点双连通图内至少有一个奇环，那么所有点都在至少一个奇环上。根据上述思想，不断地叠加环到已有的奇环上，觉得这个结论很对。但我们需要一个严谨的证明。

先考虑一个奇环。然后对任意环外点 x，尝试联络奇环。考虑奇环上的任意一个点 y，那么 x,y 至少在一个环上。如果这个环跟奇环有交点，那么 x\to y 两条路各取第一个交点就可以归约到上述有一段公共部分的两个环的情况。否则的话，另找一个奇环上的点 z\neq y 满足存在 x\to z 的不交于奇环的路径（根据点双性一定存在 z），尝试从它与 x\to y 两条路除了端点的部分不交地走到 x。如果成功了，那又可以归约；如果交上了，立刻停止，此时形成了环叠环叠环，归约两次即可。

最后就对每个点双跑一下染色，失败了的话内部的点全部可行。最后数不可行的。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2010;
int n,m,qu;
int to[N][N];
vector<int> nei[N];
int dfn[N],low[N],nowdfn;
int stk[N],top;
bool shd[N];
int col[N];
bool dfs(int x,int c=1){
    if(col[x]){
        if(col[x]==c)return true;
        return false;
    }
    col[x]=c;
    for(int i=0;i<nei[x].size();i++){
        int y=nei[x][i];
        if(shd[y]&&!dfs(y,3-c))return false;
    }
    return true;
}
bool isans[N];
void tar(int x=1,int fa=0){
    stk[top++]=x;
    dfn[x]=low[x]=++nowdfn;
    if(!fa&&nei[x].size()==0)return;
    for(int i=0;i<nei[x].size();i++){
        int y=nei[x][i];
        if(y==fa){fa=-1;continue;}
        if(!dfn[y]){
            tar(y,x),low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y]){
                vector<int> v;
                while(true){
                    int z=stk[--top];
                    v.pb(z);shd[z]=true;
                    if(z==y)break;
                }
                v.pb(x);shd[x]=true;
                if(!dfs(x)){
                    for(int j=0;j<v.size();j++)isans[v[j]]=true;
                }
                for(int j=0;j<v.size();j++)shd[v[j]]=false,col[v[j]]=0;
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
void mian(){//remember to make it first
    nowdfn=top=0;
    for(int i=1;i<=2*n;i++)nei[i].clear(),dfn[i]=isans[i]=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)to[i][j]=i!=j;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        to[x][y]=to[y][x]=0;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(to[i][j])nei[i].pb(j);
    for(int i=1;i<=n;i++)if(!dfn[i])tar(i);
    int ans=0;
    for(int i=1;i<=n;i++)ans+=isans[i];
    printf("%d\n",n-ans);
}
int main(){
    while(cin>>n>>m,n)mian();
    return 0;
}