二分图检测 ( 并不一能AC )
#include <iostream>
#include <vector>
#define r() fast_read()
using namespace std;
inline int fast_read(void) {
int n = 0, sign = 1;
char c = getchar();
while (not isdigit(c)) {
if (c == '-') sign = ~0;
c = getchar();
}
while (isdigit(c)) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
int T, n, m;
enum Color { UNKNOWN = 0, BLUE, RED };
// 使用DFS 判断一个图是不是二分图(二部图)bipartition
inline bool DFS(vector<int> g[],
Color colors[],
int curr,
Color color) {
colors[curr] = color;
for (const int nei : g[curr]) {
if (colors[nei] == color) return false; // conflict
if (colors[nei] == UNKNOWN and not DFS(g, colors, nei,
color == BLUE ? RED : BLUE)) return false;
}
return true;
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
T = r();
for (int t = 1; t <= T; ++t) {
printf("Scenario #%d:\n", t);
n = r(), m = r();
vector<int> g[n + 1];
Color colors[n + 1];
fill(colors, colors + 1 + n, UNKNOWN);
for (int u, v; m--;) {
u = r(), v = r();
g[u].emplace_back(v);
g[v].emplace_back(u);
}
bool flag = 0;
for (int u = 1; u <= n; ++u)
if (colors[u] == UNKNOWN and not DFS(g, colors, u, BLUE)) {
flag = 1;
break;
}
if (flag) puts("Suspicious bugs found!");
else puts("No suspicious bugs found!");
putchar(10);
}
// fclose(stdin);
return ~~(0 ^ 0);
}