SP3377 BUGLIFE - A Bug's Life 做题记录
一个虫子是通讯录当且仅当关系构成的图包含奇环，而一张图是二分图当且仅当这个图没有奇环，于是我们可以通过染色法判定二分图。单个测试点时间复杂度 \(O(n)\)。
点击查看代码
void dfs(int now,int col) {
c[now]=col;
for(auto v:G[now]) {
if(!c[v]) dfs(v,3-col);
else if(c[v]==c[now]) {
ans=1;
return ;
}
}
}
void work() {
ans=0;
in2(n,m);
For(i,1,m) {
int x,y;
in2(x,y);
pb(G[x],y);
pb(G[y],x);
}
For(i,1,n) if(!c[i]) dfs(i,1);
if(!ans) printf("No suspicious bugs found!\n");
else printf("Suspicious bugs found!\n");
For(i,1,n) G[i].clear();
m0(c);
}