<>

题目大意：

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

解题分析：

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

#include 
     
      using namespace std;const int N = 1e5+5;typedef long long ll;int n,num1,num2;vector
      
       G[N];int vis[N];void dfs(int u,int id){    if(id&1)num1++;    else num2++;    vis[u]=1;    for(auto v:G[u]){        if(!vis[v])dfs(v,id^1);    }}int main(){    cin>>n;    for(int i=1;i
      
     

 

 

 

2018-08-15