题解 | #图的增边#

#include <bits/stdc++.h>

using namespace std;
/*
* 二分图,图的所有顶点被分为两个部分,每个部分中的某些可能是相连的,但是在相同部分的顶点之间不连接;
*/



// 染色操作!
void track(int cur,int color,vector<int>& edges,vector<vector<int>>& graph){
    if(edges[cur] != -1) return ;
    edges[cur] = color;
    color ^= 1;
    for(auto nx : graph[cur]){
        track(nx, color, edges,graph);
    }
}



int main() {
    int n,m,u,v;
    cin >> n >> m;
    vector<int> edges(n+1,-1);
    vector<vector<int>> graph(n+1,vector<int>());
    
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    long long count = 0;

    /*
    *   通过 深度优先搜索遍历全图,对图进行标记!
    */
    track(1,1,edges,graph);

    for(int i = 1; i <= n; i++){
        if(edges[i] == 1) count ++;
    }

    count *= n-count;


    cout << count - m << endl;

    return 0;
}