Submission #1157269

---

Source Code Expand

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef vector<pii> vii;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()

void dfs (int x, const vvi &g, vi &color, vi &comp)
{
    comp.pb(x);
    for (int dest : g[x]) if (color[dest] == -1)
    {
        color[dest] = (color[x] ^ 1);
        dfs(dest, g, color, comp);
    }
}

void solve (int n)
{
    vvi g(n);
    int m;
    cin >> m;
    forn (i, m)
    {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].pb(v);
        g[v].pb(u);
    }

    int cnt1 = 0, cntodd = 0, cntev = 0;
    vi color(n, -1);
    forn (i, n) if (color[i] == -1)
    {
        vi comp;
        color[i] = 0;
        dfs(i, g, color, comp);

        if (sz(comp) == 1)
            cnt1++;
        else
        {
            bool ok = true;
            for (int x : comp) for (int dest : g[x])
                ok &= (color[x] != color[dest]);
            if (ok)
                cntev++;
            else
                cntodd++;
        }
    }

    ll ans = (ll)cnt1 * (ll)cnt1 + 2 * (ll)(n - cnt1) * cnt1;
    ans += 2 * (ll)cntev * (ll)cntev;
    ans += (ll)cntodd * (ll)cntodd + 2 * (ll)cntev * (ll)cntodd;
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while (cin >> n)
        solve(n);
}

Submission Info

Judge Result