CodeForces - 862B Mahmoud and Ehab and the bipartiteness（dfs）

题意：给出一个二分图，求不形成环的情况下还能连接多少条边。

题记：将二分图染色分为两部分，奇数和偶数。奇数的点数量为a，偶数的点数量为b。那么这个二分图总共可以连接ab条边。题目已经连了n-1条边，所有还可以连ab-(n-1)=a*b-n+1。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
using namespace std;
#define F first
#define S second
#define ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define lowbit(x) ((x)&-(x))
typedef pair<int,int> PII;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int dis[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
const int MOD=1e9+7;
const int N=1e5+10;
vector<int> g[N];
ll a,b;
void dfs(int u,int v,int w){
    if(w==1) a++;
    else b++;
    for(int i=0;i<g[v].size();i++){
        if(u==g[v][i]) continue;
        dfs(v,g[v][i],1-w);
    }
}

int main(){
    //IOS;
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    a=b=0;
    dfs(0,1,0);
    cout<<a*b-n+1<<endl;
    return 0;
}

本文地址：https://blog.csdn.net/weixin_45809826/article/details/108167197