Bipartite graph bicoloring with DFS

bicoloring.cpp

// https://codeforces.com/contest/862/problem/B
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void bicoloring(unordered_map<ll, vector<ll>> &graph, vector<ll> &color, ll curNode, ll curColor = 1) {
    if (color[curNode]) return;
    color[curNode] = curColor;
    for (ll i : graph[curNode]) {
        bicoloring(graph, color, i, -curColor);
    }
}

int main() {
    ll n;
    cin >> n;
    // The given graph is bipatite
    unordered_map<ll, vector<ll>> graph;
    for (ll i = 0; i < n - 1; i++) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<ll> color(n + 1);
    bicoloring(graph, color, 1);
    ll l = 0, r = 0;
    for (ll i : color) {
        l += i == 1;
        r += i == -1;
    }
    // Number of edges can be added so that the graph is still bipartite
    // Loop (such as (1, 2), (2, 1)) and repeated edges is not allowed
    cout << l * r - (n - 1);
}