题意：判断一个图是否为二分图。
?

——>>直接dfs。

[cpp]? #include??
#include??
#include??
?
using namespace std;?
?
const int maxn = 2000 + 10;?
int color[maxn], n, m;?
bool vis[maxn];?
vector G[maxn];?
?
bool dfs(int u)???? //判断u的在的连通分支是否为二分图??
{?
??? vis[u] = 1;?
??? int i, len = G[u].size();?
??? for(i = 0; i < len; i++)?
??? {?
??????? int v = G[u][i];?
??????? if(color[u] == color[v]) return false;?
??????? if(!color[v])?
??????? {?
??????????? color[v]= 3 - color[u];?
??????????? if(!dfs(v)) return false;?
??????? }?
??? }?
??? return true;?
}?
?
int main()?
{?
??? int cnt = 1, T, i, x, y;?
??? scanf("%d", &T);?
??? while(T--)?
??? {?
??????? scanf("%d%d", &n, &m);?
??????? for(i = 0; i <= n; i++) G[i].clear();?
??????? for(i = 1; i <= m; i++)?
??????? {?
??????????? scanf("%d%d", &x, &y);?
??????????? G[x].push_back(y);?
??????????? G[y].push_back(x);?
??????? }?
??????? memset(color, 0, sizeof(color));?
??????? memset(vis, 0, sizeof(vis));?
??????? printf("Scenario #%d:\n", cnt++);?
??????? bool ok = 1;?
??????? for(i = 1; i <= n; i++)?
??????? {?
??????????? if(!vis[i])?
??????????? {?
??????????????? color[i] = 1;?
??????????????? if(!dfs(i))?
??????????????? {?
??????????????????? ok = 0;?
??????????????????? break;?
??????????????? }?
??????????? }?
??????? }?
??????? if(ok) printf("No suspicious bugs found!\n\n");?
??????? else printf("Suspicious bugs found!\n\n");?
??? }?
??? return 0;?
}?

#include
#include
#include

using namespace std;

const int maxn = 2000 + 10;
int color[maxn], n, m;
bool vis[maxn];
vector G[maxn];

bool dfs(int u)???? //判断u的在的连通分支是否为二分图
{
??? vis[u] = 1;
??? int i, len = G[u].size();
??? for(i = 0; i < len; i++)
??? {
??????? int v = G[u][i];
??????? if(color[u] == color[v]) return false;
??????? if(!color[v])
??????? {
??????????? color[v]= 3 - color[u];
??????????? if(!dfs(v)) return false;
??????? }
??? }
??? return true;
}

int main()
{
??? int cnt = 1, T, i, x, y;
??? scanf("%d", &T);
??? while(T--)
??? {
??????? scanf("%d%d", &n, &m);
??????? for(i = 0; i <= n; i++) G[i].clear();
??????? for(i = 1; i <= m; i++)
??????? {
??????????? scanf("%d%d", &x, &y);
??????????? G[x].push_back(y);
??????????? G[y].push_back(x);
??????? }
??????? memset(color, 0, sizeof(color));
??????? memset(vis, 0, sizeof(vis));
??????? printf("Scenario #%d:\n", cnt++);
??????? bool ok = 1;
??????? for(i = 1; i <= n; i++)
??????? {
??????????? if(!vis[i])
??????????? {
??????????????? color[i] = 1;
??????????????? if(!dfs(i))
??????????????? {
??????????????????? ok = 0;
??????????????????? break;
??????????????? }
??????????? }
??????? }
??????? if(ok) printf("No suspicious bugs found!\n\n");
??????? else printf("Suspicious bugs found!\n\n");
??? }
??? return 0;
}

?