Codeforces 862B （二分图染色）

<题目链接>

题目大意：

给出一个有n个点的二分图和n-1条边，问现在最多可以添加多少条边使得这个图中不存在自环，重边，并且此图还是一个二分图。

解题分析：

此题不难想到，假设二分图点集数量分别为x,y,添加最多的边数，无非就是x*y-(n-1)，于是，我们利用dfs对所有点进行染色，进而将其划分为两个集合。

1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 1e5+5;
5typedef long long ll;
6int n,num1,num2;
7vector<int>G[N];
8int vis[N];
9
10void dfs(int u,int id){
11    if(id&1)num1++;
12    else num2++;
13    vis[u]=1;
14    for(auto v:G[u]){
15        if(!vis[v])dfs(v,id^1);
16    }
17}
18int main(){
19    cin>>n;
20    for(int i=1;i<n;i++){
21        int u,v;scanf("%d%d",&u,&v);
22        G[u].push_back(v);
23        G[v].push_back(u);
24    }
25    dfs(1,0);
26    ll ans=(ll)num1*(ll)num2-n+1;
27    printf("%lld\n",ans);
28}

2018-08-15