POJ-2942 Knights of the Round Table（補圖+點雙連通分量+奇圈+染色判斷二分圖+結論）

連結：http://poj.org/problem?id=2942

題意：多組樣例。亞瑟王要召喚騎士在圓桌會議。n個騎士，m個憎恨關系，一個騎士不能和他憎恨的騎士坐在一塊。亞瑟王要求來開會的騎士的個數必須是奇數，在此條件下，求開除最少的騎士。（注意一個騎士不能開會，至少三個騎士才能開會。）

思路：我們建補圖，這樣有邊的人都能做一塊，然後再求點雙，求出點雙後，再判斷能不能形成奇圈。這裡有現成的結論。

（1） 如果一個雙連通分量内（即點雙）的某些頂點在一個奇圈中（即雙連通分量含有奇圈），那麼這個雙連通分量的其他頂點也在某個奇圈中；

（2）如果一個雙連通分量含有奇圈，則他必定不是一個二分圖。反過來也成立，這是一個充要條件。

這樣每求出一個點雙後，dfs染色判斷是不是二分圖就好了。

參考部落格：https://blog.csdn.net/lyy289065406/article/details/6756821

PS：這裡又新加了一種存邊求點雙的方法，但不知道為啥，有的題會出錯，以後就用存點求點雙啦。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long  long
using namespace std;
const int N = 1e3+10;
const int M = 1e6+10;
struct node
{
    int from,to,nxt;
    bool use;
}g[M];
int n,m;
bool mp[N][N];
int head[N],cnt;
int dfn[N],low[N],id,sta[N],top;
bool bcc[N],can[N];
int color[N];
int ans;
inline int Read()
{
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
inline void Write(int a)
{
    if(a>9)
        Write(a/10);
    putchar(a%10+'0');
}
inline void Init()
{
    ans=cnt=id=top=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            mp[i][j]=0;
    for(int i=1;i<=n;i++)
        can[i]=dfn[i]=0,head[i]=-1;
}
inline void add(int u,int v)
{
    g[cnt].from=u; g[cnt].to=v; g[cnt].use=0; g[cnt].nxt=head[u]; head[u]=cnt++;
}
inline bool dfs(int u)
{
    int v;
    for(int i=head[u];~i;i=g[i].nxt)
    {
        v=g[i].to;
        if(bcc[v])
        {
            if(color[v]==-1)
            {
                color[v]=(color[u]^1);
                return dfs(v);
            }
            else if(color[u]==color[v]) return 1;
        }
    }
    return 0;
}
inline void check(int x,int u)
{
    int i;
    for(i=1;i<=n;i++) bcc[i]=0;
	while(sta[top]!=x)
		bcc[sta[top--]]=1;
    bcc[sta[top--]]=1;
    bcc[u]=1;
    for(i=1;i<=n;i++) color[i]=-1;
    color[u]=0;
    if(dfs(u))
    {
        for(i=1;i<=n;i++)
            if(bcc[i]) can[i]=1;
    }
}
inline void tarjan(int u)
{
    int v;
    dfn[u]=low[u]=++id;
    for(int i=head[u];~i;i=g[i].nxt)
    {
        v=g[i].to;
        if(g[i].use) continue;
        g[i].use=g[i^1].use=1;
        if(!dfn[v])
        {
			sta[++top]=v;
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) check(v,u);
        }
        else
            low[u]=min(low[u],dfn[v]);
    }
}
int main()
{
    int u,v;
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        Init();
        while(m--)
        {
            u=Read(); v=Read();//scanf("%d%d",&u,&v);
            mp[u][v]=mp[v][u]=1;
        }
        for(u=1;u<=n;u++)
            for(v=u+1;v<=n;v++)
                if(!mp[u][v])
                    add(u,v),add(v,u);
        for(int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(i);
        for(int i=1;i<=n;i++) if(!can[i]) ans++;
        //printf("%d\n",ans);
        Write(ans); putchar('\n');
    }
    return 0;
}           

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long  long
using namespace std;
const int N = 1e3+10;
const int M = 1e6+10;
struct node
{
    int from,to,nxt;
    bool use;
}g[M];
int n,m;
bool mp[N][N];
int head[N],cnt;
int dfn[N],low[N],id,sta[M],top;
bool bcc[N],can[N];
int color[N];
int ans;
inline int Read()
{
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
inline void Write(int a)
{
    if(a>9)
        Write(a/10);
    putchar(a%10+'0');
}
inline void Init()
{
    ans=cnt=id=top=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            mp[i][j]=0;
    for(int i=1;i<=n;i++)
        can[i]=dfn[i]=0,head[i]=-1;
}
inline void add(int u,int v)
{
    g[cnt].from=u; g[cnt].to=v; g[cnt].use=0; g[cnt].nxt=head[u]; head[u]=cnt++;
}
inline bool dfs(int u)
{
    int v;
    for(int i=head[u];~i;i=g[i].nxt)
    {
        v=g[i].to;
        if(bcc[v])
        {
            if(color[v]==-1)
            {
                color[v]=(color[u]^1);
                return dfs(v);
            }
            else if(color[u]==color[v]) return 1;
        }
    }
    return 0;
}
inline void check(int x)
{
    int i;
    for(i=1;i<=n;i++) bcc[i]=0;
    do
    {
        i=sta[top--];
        bcc[g[i].from]=1;
        bcc[g[i].to]=1;
    }while(g[i].from!=x);
    for(i=1;i<=n;i++) color[i]=-1;
    color[x]=0;
    if(dfs(x))
    {
        for(i=1;i<=n;i++)
            if(bcc[i]) can[i]=1;
    }
}
inline void tarjan(int u)
{
    int v;
    dfn[u]=low[u]=++id;
    for(int i=head[u];~i;i=g[i].nxt)
    {
        v=g[i].to;
        if(g[i].use) continue;
        g[i].use=g[i^1].use=1;
        sta[++top]=i;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) check(u);
        }
        else
            low[u]=min(low[u],dfn[v]);
    }
}
int main()
{
    int u,v;
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        Init();
        while(m--)
        {
            u=Read(); v=Read();//scanf("%d%d",&u,&v);
            mp[u][v]=mp[v][u]=1;
        }
        for(u=1;u<=n;u++)
            for(v=u+1;v<=n;v++)
                if(!mp[u][v])
                    add(u,v),add(v,u);
        for(int i=1;i<=n;i++)
            if(!dfn[i]) tarjan(i);
        for(int i=1;i<=n;i++) if(!can[i]) ans++;
        //printf("%d\n",ans);
        Write(ans); putchar('\n');
    }
    return 0;
}