(AtCoder Beginner Contest 282) D - Make Bipartite 2(二分图)

给定一个n个点m条边的图，请你在其中加一条边使得整个图G是二分图，问有多少种可能。（已有的边不能加）

解题思路：

首先我们要知道，二分图内是没有长度为奇数的回路的
所以如果我们将一个图内的点分为两部分，这两部分的点互相连起来的不重复的点都是满足二分图的
例如：
5个点分为两组：[1,2] [3,5]
此时我们所有可以连起来的边为：1-3,1-4,1-5,2-3,2-4,2-5
保证组内的点没有边即保证了没有长度为奇数的回路

我们考虑三种情况：

1. 当前只有一个联通分量，且该联通分量内本身为一个二分图：
   此时我们只需要染色后得到c1,c2(将图内的点分为两部分),（c1*c2-m）就是答案，表示所有满足二分图的边除去已有的边。
2. 当前有多个联通分量，且各联通分量内部都为二分图：
   此时我们对其中一个联通分量染色后得到(res1 += (c1*c2))所有可能的边,(res2 += (c1+c2) * (n-(c1+c2)) )当前联通分量可以和其他联通分量之间内连多少条边
   最终我们能够得到res1(所有可能连的边),res2(各联通分量之间连起来的边)，但是因为res2在求解的过程中，各联通分量会对同一条边计算两次，所以我们最终的答案为:ans = res1+res2/2-m;
3. 如果任意联通分量中存在非二分图，那么不论怎么加边都无法保证整个图内没有长度为奇数的回路，所以答案是0

代码实现：

#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 2e5 + 10, inf = 0x3f3f3f3f;
vector<int> e[N];
int g[N];
int c1,c2;

bool dfs(int u,int col){//染色+计数
	g[u] = col;
	c1 += col==1;
	c2 += col==2;
	for(auto v:e[u]){
		if(g[v] == g[u]) return false;
		if(!g[v]){
			if(!dfs(v,3-col)) return false;;
		}
	}
	return true;
}
void solve() {
	int n,m;
	cin>>n>>m;
	for(int i = 1;i <= m;++i){
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	int res1 = 0,res2 = 0;
	for(int i = 1;i <= n;++i){
		if(!g[i]){
			c1 = c2 = 0;
			if(!dfs(i,1)){//如果存在非二分图，无法加边
				cout<<0<<endl;
				return;
			};
			res1 += c1*c2;
			res2 +=(c1+c2)*(n-c1-c2);
		}
	}
	int ans = res1+res2/2-m;//第一二种情况合并起来，因为如果只有一个联通分量，res2为0
	cout<<ans<<endl;

}
int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;
//	cin >> tt;
	while (tt--) solve();


	return 0;
}