题面还好,就不描述了
重点说题解:
由于仇恨关系不好处理,所以可以搞补图存不仇恨关系,
如果一个桌子上面的人能坐到一起,显然他们满足能构成一个环
所以跑点双联通分量
求点双联通分量我用的是向栈中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 ;
}