MENU

Mahmoud and Ehab and the bipartiteness | ACM

April 6, 2019 • ACM

题目大意给出n个点,n-1条边
求再最多再添加多少边使得图的边数最大且仍未二分图
输入数据第一行是一个整数n,代表点的个数
后面紧跟着n-1行,每一行有两个整数,代表这两个点相连
数据输出输出如果要使图的边数最大且仍为二分图所需要添加的边数
样例输入3
1 2
1 3
样例输出0
样例输入5
1 2
2 3
3 4
4 5
样例输出2

思路简述

  • 既然是二分图,我们就需要从数据中将二分图构建出来,用染色法构建二分图

    • 所谓染色法,就是将每一个相连的点赋予不同的两种权值(例如0和1),遍历一遍相连的点,这些点就被分成了两个集合,权值为0和权值为1的集合。
  • 至于计算要加多少条边,是没有必要的,在我们得出权值为0和权值为1的集合中分别有n,m个点时,我们可以求出此图的最大变数为n*m,我们用(n*m)- (n-1)即可得出想要的结果。
#include<stdio.h>
#include<vector>

using namespace std;
vector<long long> x[100005];
long long count[2];

void dfs(int a,int pa,int col)
{
    count[col]++;
    int len = x[a].size();
    for(int i = 0;i < len;i++)
    {
        if(x[a][i] != pa)
        dfs(x[a][i],a,!col);
    }
}
    
int main()
{
    int n;
    int a,b;
    while(~scanf("%d",&n))
    {
        for(int i = 1;i < n;i++)
        {
            scanf("%d %d",&a,&b);
            x[a].push_back(b);
            x[b].push_back(a);
        }
        dfs(1,0,0);
//        printf("%d\n",count[0]);
        printf("%lld\n",count[0]*count[1]-n+1);
 }
    return 0;
}
  • 这一个图我改了好几个版本,一直wa在了第九个样例上面,改了一晚上,最后发现是我的数组少开了一个0;
Archives QR Code
QR Code for this page
Tipping QR Code