O(n+m)

int h[N], e[M], ne[M], w[M], idx; //memset(h, -1, sizeof h);
int color[N];                     //0表示未染色，1表示白色，2表示黑色

void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!color[v])
        {
            if (!dfs(v, 3 - c))
            {
                return 0;
            }
        }
        else if (color[v] == c)
        {
            return 0;
        }
    }
    return 1;
}

bool check() //返回1为二分图
{
    memset(color, 0, sizeof color);
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                return 0;
            }
        }
    }
    return 1;
}