Submission #3407672

---

Source Code Expand

/*input
100000 6
1 2
2 3
3 1
4 5
5 6
6 7
5 5
1 2
2 3
3 1
5 4
5 1
6 5
1 2
2 3
3 4
4 5
5 6
*/
#include <bits/stdc++.h>
#define db(x) cout<<#x<<"="<<(x)<<" "
#define el cout<<endl
using namespace std;
const int MXN = 1e6 + 10;

int M, N; long long ans;
int fus[MXN], c[MXN], cl[MXN]; long long sz[MXN][4];
int GF(int x) {
    if (x == fus[x])
        return x;
    int r = GF(fus[x]);
    c[x] ^= c[fus[x]];
    return fus[x] = r;
}
int main() {
    cin >> N >> M; // n = N;
    iota(fus, fus + N + 1, 0);
    for (int t = 1; t <= M; ++t) {
        int x, y;
        cin >> x >> y;
        int rx = GF(x), ry = GF(y);
        if (rx == ry) {
            if (c[x] ^ c[y] ^ 1) {
                cl[rx] = 1;
            } else {
            }
        } else {
            fus[rx] = ry;
            cl[ry] |= cl[rx];
            c[rx] = c[x] ^ c[y] ^ 1;
        }
    }
    for (int i = 1; i <= N; ++i)
    {
        int r = GF(i);
        sz[r][c[i]]++;
    }
    for (int i = 1; i <= N; ++i)
    {
        int r = GF(i);
        if (i == r) {
            //db(cl[r]), db(r), db(sz[i][0]), db(sz[i][1]), el;
            if (!cl[r]) {
                ans += sz[i][0] * sz[i][1];
            }
            else {
                long long t = sz[i][0] + sz[i][1];
                ans += (t - 1) * t / 2;
            }
        }
    }
    cout  << ans - M << endl;
    return 0;
}

Submission Info

Judge Result