《Make Bipartite 2》

思维，二分图

 这个简单图可以有两种情况：

　　1.全部点都通过边连起来，即连通分量只有一个，其自己

　　2.还有有些点没有全部连起来，即有多个连通分量

1.不管上面哪一种情况，如果对图跑一个二分图染色O（n+m）,如果染色失败，则都是返回0，因为这时，不管再连上那一边都不是二分图了

下面我们保证跑一个二分图染色O（n+m）,如果染色成功：

2.现在我们假设各个点之间都有边，即一共有n*(n-1)/2条边

　　　　（1）对于只有一个连通分量来说: 连上相同颜色的点的边和已经连好的边（m），都是使二分图不合法的，除此之外都是合法的

　　则假设这个连通分量上有w个白点，b个黑点，则不合法的边为 w*(w-1)/2+b*(b-1)/2+m条

　　则正确答案为ans=n*(n-1)/2-（w*(w-1)/2+b*(b-1)/2+m）；

　　　　（2）对于有多个连通分量来说：两个不同的连通分量上的任意点相连,都还是二分图

　　对于相同连通分量上的相同颜色的点相连是不合法的，同时已经连好的边（m）也是不合法的

于是：

 这里循环相加的是各个连通分量上黑点相连的边数与白点相连的边数

即我们在写dfs跑二分图染色时，可以返回这个连通分量上黑点与白点的个数

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 const int N = 2 * 1e5 + 2;
 7 typedef long long ll;
 8 typedef pair<int, int> PII;
 9 int color[N], n, m;
10 vector<int> sides[N];
11 PII dfs(int x, int c)
12 {
13     PII p = {0, 0};
14     color[x] = c;
15     if (c == 1)
16         p.first++;
17     else
18         p.second++;
19     for (int i = 0; i < sides[x].size(); i++)
20     {
21         int j = sides[x][i];
22         PII res;
23         if (!color[j])
24             res = dfs(j, -c);
25         else if (color[j] == c)
26             // 表示不构成二分图
27             return {-1, -1};
28         if (res.first == -1 && res.second == -1)
29             return {-1, -1};
30         else
31         {
32             p.first += res.first;
33             p.second += res.second;
34         }
35     }
36     return p;
37 }
38 int main()
39 {
40     cin >> n >> m;
41     for (int i = 1; i <= m; i++)
42     {
43         int a, b;
44         scanf("%d%d", &a, &b);
45         sides[a].push_back(b), sides[b].push_back(a);
46     }
47     ll ans = (ll)n * (n - 1) / 2 - m;
48     for (int i = 1; i <= n; i++)
49     {
50         if (!color[i])
51         {
52             PII p = dfs(i, 1);
53             // p.first表示这个连通分量中染色白色的个数（color==1）,p.second 表示这个连通分量中染色黑色的个数；
54             if (p.first == -1 && p.second == -1)
55             {
56                 cout << 0;
57                 return 0;
58             }
59             ans -= (ll)p.first * (p.first - 1) / 2;
60             ans -= (ll)p.second * (p.second - 1) / 2;
61         }
62     }
63     cout << ans;
64     return 0;
65 }