Codeforces 862 B Mahmoud and Ehab and the bipartiteness（二分图染色）

题目地址
题意：给你n个点，n-1条边，他们构成了一个二分图，让你尽可能的加边，使得最后得到得图还是二分图。
思路：对二分图进行染色，，让他分为2个集合，然后我们对这两个集合里得每一条边得相互连接，这样得话最后的图还是二分图了。

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define N 100010
#define LL __int64
#define inf 0x3f3f3f3f
#define lson l,mid,ans<<1
#define rson mid+1,r,ans<<1|1
#define getMid (l+r)>>1
#define movel ans<<1
#define mover ans<<1|1
using namespace std;
vector<int> mapp[N];
int color[N];
bool vis[N];
void init(int n) {
for (int i = 1; i <= n; i++) {
mapp[i].clear();
}
memset(vis, false, sizeof(vis));
memset(color, 0, sizeof(color));
}
void dfs(int u) {
for (int i = 0; i < mapp[u].size(); i++) {
if (vis[mapp[u][i]]) continue;
color[mapp[u][i]] = color[u] ^ 1;
vis[mapp[u][i]] = true;
dfs(mapp[u][i]);
}
}
int main() {
cin.sync_with_stdio(false);
LL n, x, y;
while (cin >> n) {
init(n);
for (int i = 1; i < n; i++) {
cin >> x >> y;
mapp[x].push_back(y);
mapp[y].push_back(x);
}
x = 0, y = 0;
dfs(1);
for (int i = 1; i <= n; i++) {
if (color[i]) x++;
else y++;
}
cout << x*y - (n - 1) << endl;
}
return 0;
}

最后

以上就是心灵美帽子为你收集整理的Codeforces 862 B Mahmoud and Ehab and the bipartiteness（二分图染色）的全部内容，希望文章能够帮你解决Codeforces 862 B Mahmoud and Ehab and the bipartiteness（二分图染色）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。