时间复杂度:O(N + M)
bool dfs(int u, int c)
{
color[u] = c;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (color[j])
{
if (color[j] == c) return false;
}
else if (!dfs(j, 3 - c)) return false;
}
return true;
}
bool check()
{
memset(color, 0, sizeof color);
for (int i = 1; i <= n; i ++ )
if (color[i] == 0)
if (!dfs(i, 1))
return false;
return true;
}