POJ 2942 Knights of the Round Table 补图+tarjan求点双联通分量+二分图染色+debug

题面还好,就不描述了

---

重点说题解:

由于仇恨关系不好处理,所以可以搞补图存不仇恨关系,

如果一个桌子上面的人能坐到一起,显然他们满足能构成一个环

所以跑点双联通分量

求点双联通分量我用的是向栈中push边的方法

请注意:只向栈中push树枝边

这样每次一对父子(u,v)

如果low[v]<=dfn[u] 显然u是v所在点双联通分量的割点

所以栈中边(u,v)之前的边都pop,他们连接的点构成点双联通分量

我们找到一个点双联通分量之后,由于要求奇数个人坐一桌

所以满足存在奇环,dfs染色即可

注意割点可能属于很多点双联通分量,所以染完色之后需要给他把颜色去掉

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<stack>

 #define N 1010

 using namespace std;

 int n,m,head[N],adj[N][N],ans,dfn[N],low[N],ok[N],ecnt,indx,clr[N],inst[N];

 int read()

 {

     int ret=,neg=;

     char j=getchar();

     for (;j<'' || j>'';j=getchar())

     if (j=='-') neg=-;

     for (;j<='' && j>='';j=getchar())

     ret=ret*+j-'';

     return ret*neg;

 }

 struct edge

 {

     int u,v,nxt;

 }e[N*N];

 stack <edge> stk;

 stack <int> tmp;

 void add(int u,int v)

 {

     e[++ecnt].u=u;

     e[ecnt].v=v;

     e[ecnt].nxt=head[u];

     head[u]=ecnt;

 }

 void getG()//还是推荐链式前向星存图= =

 {

     for (int i=,u,v;i<=m;i++)

     {

     u=read(),v=read();

     adj[u][v]=;

     adj[v][u]=;

     }

     for (int i=;i<=n;i++)

     for (int j=;j<=n;j++)

         if (adj[i][j]== && i!=j) add(i,j);

 }

 int dfs(int u,int nw)//染色

 {

     int ret=;

     for (int i=head[u];i;i=e[i].nxt)

     {

     int v=e[i].v;

     if (inst[v]==)

     {

         if (clr[v]==-)

         {

         clr[v]=-nw;

         ret&=dfs(v,-nw);

         }

         else

         if (clr[v]==nw) ret=;

     }

     }

     return ret;

 }

 void init()

 {

     memset(ok,,sizeof(ok));

     memset(head,,sizeof(head));

     memset(adj,,sizeof(adj));

     memset(inst,,sizeof(inst));

     ecnt=;

     memset(dfn,,sizeof(dfn));

     memset(clr,-,sizeof(clr));

     indx=;

     ans=;

 }

 void tar(int u,int fa)

 {

     dfn[u]=low[u]=++indx;

     for (int i=head[u];i;i=e[i].nxt)

     {

     int v=e[i].v;

     if (!dfn[v])

     {

         stk.push(e[i]);

         tar(v,u);

         low[u]=min(low[u],low[v]);

         if (low[v]>=dfn[u])//题解找双联通分量部分

         {

         while ()

         {

             edge e=stk.top();

             stk.pop();

             inst[e.u]=;

             inst[e.v]=;

             tmp.push(e.u);

             tmp.push(e.v);

             if (e.u==u && e.v==v) break;

         }

         clr[u]=;

         if (dfs(u,)==)

             while (!tmp.empty())

             {

             ok[tmp.top()]=;

             inst[tmp.top()]=;

             tmp.pop();

             }

         else while (!tmp.empty()) inst[tmp.top()]=,tmp.pop();

         clr[u]=-;

         }

     }

     else if (v!=fa)

         low[u]=min(low[u],dfn[v]);

     }

 }

 int main()

 {

     n=read();

     m=read();

     while (n || m)

     {

     init();

     getG();

     for (int i=;i<=n;i++)

         if (!dfn[i]) tar(i,-);

     for (int i=;i<=n;i++)

         ans+=ok[i];

     printf("%d\n",n-ans);

     n=read(),m=read();

     }

     return ;

 }