Solution KNIGHTS

二分图，点双联通分量

分析：我们把有憎恨关系的连上边，这样相邻骑士之间必须没有连边，这样不好考虑，我们可以建出原图的补图，这样相邻骑士之间就必须有连边了。

问题变成了有多少个点没有被任何一个奇数长度的环包含

显而易见，如果一个点双联通分量内存在奇数长度的环，那么该点双联通分量里面所有的点都至少被一个奇数长度的环包含，不然与点双联通分量这个前提相矛盾

因此我们只需要看每一个点双联通分量里面有没有奇数长度的环就可以了，没有奇数长度的环等价于图是二分图，因此我们跑一次二分图染色就可以了

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
const int maxn = 1024;
vector<int> G[maxn],dcc[maxn];
inline void addedge(int from,int to){G[from].push_back(to);}
int tmp[maxn][maxn],dfn[maxn],mark[maxn],vis[maxn],low[maxn],col[maxn],can[maxn],dcc_tot,dfs_tot,n,m;
inline void clear(){
    for(int i = 1;i <= n;i++)G[i].clear();
    for(int i = 1;i <= dcc_tot;i++)dcc[i].clear();
    dcc_tot = dfs_tot = 0;
    memset(can,0,sizeof(can));
    memset(tmp,0,sizeof(tmp));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
}
stack<int> stk;
inline void tarjan(int u,int isroot = 1){
    dfn[u] = low[u] = ++dfs_tot;
    stk.push(u);
    if(isroot && G[u].empty()){
        dcc[++dcc_tot].push_back(u);
        return;
    }
    for(int v : G[u])
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
            if(low[v] >= dfn[u]){
                dcc_tot++;
                int t;
                do{
                    t = stk.top();stk.pop();
                    dcc[dcc_tot].push_back(t);
                }while(t != v);
                dcc[dcc_tot].push_back(u);
            }
        }else low[u] = min(low[u],dfn[v]);
}
inline bool check(int i){
    memset(mark,0,sizeof(mark));
    memset(vis,0,sizeof(vis));
    memset(col,0,sizeof(col));
    for(int x : dcc[i])mark[x] = 1;
    queue<int> Q;Q.push(dcc[i][0]),vis[dcc[i][0]] = 1;
    while(!Q.empty()){
        int u = Q.front();Q.pop();
        for(int v : G[u]){
            if(!mark[v])continue;
            if(!vis[v])col[v] = col[u] ^ 1,Q.push(v),vis[v] = 1;
            else if(col[u] == col[v])return false;
        }
    }
    return true;
}
inline void solve(){
    for(int u,v,i = 1;i <= m;i++)scanf("%d %d",&u,&v),tmp[u][v] = tmp[v][u] = 1;
    for(int u = 1;u <= n;u++)
        for(int v = u + 1;v <= n;v++)
            if(!tmp[u][v])addedge(u,v),addedge(v,u);
    for(int i = 1;i <= n;i++)
        if(!dfn[i])tarjan(i);
    int ans = n;
    for(int i = 1;i <= dcc_tot;i++)
        if(dcc[i].size() >= 3 && !check(i))
            for(int x : dcc[i])can[x] = 1;
    for(int i = 1;i <= n;i++)
        ans -= can[i];
    printf("%d\n",ans);
    clear();
}
int main(){
    while(scanf("%d %d",&n,&m) && n && m)solve();
    return 0;
}

点双联通分量

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

Solution KNIGHTS