ABC282D二分图染色加乘原理统计方案

对于每个连通块，不同颜色的点可以连边；已有z条边，每条边连接都是不同颜色，所以贡献为x * y - z。
对于不同连通块，任意两点可以互相连边（颜色相同反一下即可）。

#include <stdio.h>
#define N 200005
int n, m, i, j, k, a, b, h[N], c[N], u[N*2];
long long s, x, y, z, p;
struct AB{
    int a, b, n;
} d[N*2];
void cun(int a, int b){
    d[++k].a = a, d[k].b = b;
    d[k].n = h[a], h[a] = k, u[k] = 1;
}
void dfs(int a){
    int b, i;
    x += c[a]<3, y += c[a]>2;//黑白分别多少个点
    for(i=h[a]; i; i=d[i].n){
        b = d[i].b, z += u[i];//有多少条边
        u[i] = u[i^1] = 0;
        if(!c[b]){
            c[b] = c[a] ^ 1;
            dfs(b);
        }
        else if(c[b] == c[a]) s = -1e18;//不是二分图
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=k=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        cun(a, b);
        cun(b, a);
    }
    for(i=1; i<=n; i++){
        if(c[i]) continue;
        x = y = z = 0, c[i] = 2;
        dfs(i);
        s += x*y-z + p*(x+y), p += x+y;
    }//每个连通块为x+y-z，连通块任意两点可以连边
    if(s < 0) s = 0;
    printf("%lld\n", s);
    return 0;
}