所以您写着BFS。。。
by 小菜鸟 @ 2018-08-28 20:24:42
@[小菜鸟](/space/show?uid=60489) 实则dfs(手动滑稽)
by llwanan @ 2018-08-28 20:26:23
这个搜索函数是不是有点，，，
当n=10000时你的搜索树每层有10000个点，不会爆栈吗？
by 小菜鸟 @ 2018-08-28 20:28:42
你可以参考下我的代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,tot=0,ans,num[3],head[10005],color[10005];
bool flag;
struct Edge
{
int next,to;
};
Edge E[200005];
inline void add(int u,int v)
{
E[++tot].next=head[u];
E[tot].to=v;
head[u]=tot;
}
inline void paint(int now)//从一个点开始向周围涂
{
if(flag)return;
for(register int i=head[now];i;i=E[i].next)
{
int v=E[i].to;
if(color[v]==color[now]){flag=1;return;}
if(!color[v])
{
color[v]=3-color[now];
++num[color[v]];
paint(v);
}
}
}
template<class T>inline void read(T &x)
{
x=0;
int s=1;
char c=getchar();
while(c<48||c>57){s|=!(c^45);c=getchar();}
while(c>47&&c<58){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x=s*x;
}
int main(int argc,char **argv)
{
read(n),read(m);
for(register int i=0;i<m;++i)read(u),read(v),add(u,v),add(v,u);
for(register int i=1;i<=n;i++)
if(!color[i])
{
color[i]=1;
num[1]=1;num[2]=0;
paint(i);
if(flag)
{
printf("Impossible\n");
return 0;
}
else ans+=min(num[1],num[2]);
}
printf("%d\n",ans);
}
```
大致思路就是题解里的涂色
by 小菜鸟 @ 2018-08-28 20:33:53
@[小菜鸟](/space/show?uid=60489) 已经ac，感谢
by llwanan @ 2018-08-28 21:16:45