Codeforces 862B (二分图染色)

Stella981
• 阅读 515

<题目链接>

题目大意:

给出一个有n个点的二分图和n-1条边,问现在最多可以添加多少条边使得这个图中不存在自环,重边,并且此图还是一个二分图。

解题分析:

此题不难想到,假设二分图点集数量分别为x,y,添加最多的边数,无非就是x*y-(n-1),于是,我们利用dfs对所有点进行染色,进而将其划分为两个集合。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
typedef long long ll;
int n,num1,num2;
vector<int>G[N];
int vis[N];

void dfs(int u,int id){
    if(id&1)num1++;
    else num2++;
    vis[u]=1;
    for(auto v:G[u]){
        if(!vis[v])dfs(v,id^1);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    ll ans=(ll)num1*(ll)num2-n+1;
    printf("%lld\n",ans);
}

2018-08-15

点赞
收藏
评论区
推荐文章
小天 小天
1年前
图数据库简介
概况图数据库(Graphdatabase,GDB)是一个使用图结构进行语义查询的数据库,它使用节点、边和属性来表示和存储数据。该系统的关键概念是图,它直接将存储中的数据项,与数据节点和节点间表示关系的边的集合相关联。图形数据库应用场景非常
Stella981 Stella981
2年前
Python绘制拓扑图(无向图)、有向图、多重图。最短路径计算
前言:数学中,“图论”研究的是定点和边组成的图形。计算机中,“网络拓扑”是数学概念中“图”的一个子集。因此,计算机网络拓扑图也可以由节点(即顶点)和链路(即边)来进行定义和绘制。延伸:无向图两个节点之间只有一条线相连接,且没有方向。 有向图两个节点之间只有一条线相连接,且有方向。方向可以单向,也可以双向。 多重图两个节点之
Stella981 Stella981
2年前
Codeforces Round #611 (Div. 3)
原题面:https://codeforces.com/contest/1283(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fcodeforces.com%2Fcontest%2F1283)A.MinutesBeforetheNewYear题目大意:给定时间,问距离零点
Stella981 Stella981
2年前
HDU 3416 Marriage Match IV (Dijkstra+最大流)
题意:N个点M条边的有向图,给定起点S和终点T,求每条边都不重复的ST的最短路有多少条。分析:首先第一步需要找出所有可能最短路上的边。怎么高效地求出呢?可以这样:先对起点S,跑出最短路;对于每条边e(u,v,w),若d\u\wd\v\。那么e就是最短路上的一条边。在前向星存储的图中遍历即可。网上还有题解用的方法是分别从S和T跑两
Stella981 Stella981
2年前
LeetCode 5561. 获取生成数组中的最大值
文章目录1\.题目2\.解题1\.题目给你一个整数n。按下述规则生成一个长度为n1的数组nums:nums00nums11当2<2i<n时,nums2inumsi
Stella981 Stella981
2年前
POJ 1195 Mobile phones(二维树状数组)
题目链接:http://poj.org/problem?id1195(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fpoj.org%2Fproblem%3Fid%3D1195)题意是有四种操作。当n0时:输入一个m表示初始化矩阵(m\m且值都为0)。
Stella981 Stella981
2年前
GYM 101755 K.Video Reviews 【贪心】+【二分】
<题目链接(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fgym%2F101755%2Fproblem%2FK)\题目大意:一家公司想让n个人给他们的产品评论,所以依次去找这n个人,第i个人会评论当且仅当已经有ai个人评论或他确
Stella981 Stella981
2年前
Graph Coarsening And multi
Coarsening\何慧,胡铭曾,张宏莉,裴晓峰,&杨志.(2005).网络拓扑图多级分割塌缩阶段算法改进.华中科技大学学报:自然科学版,33(S1),8285.\图塌缩阶段是将图中联系较强部分粘合起来作为一个整体,并暂时从图中隐藏掉.这样经过多次塌缩后,使图变小.例如一个复杂的数千条边的图会经塌缩阶
Stella981 Stella981
2年前
HugeGraph图数据库各类索引功能对比
HugeGraphDatabaseIndexHugeGraph图数据库的索引支持比较全面,图数据库的索引一般包括几方面:图索引/边索引(graphindex):主要用于加速获取顶点的关联边,一般使用邻接表或十字链表等方式,也可以使用hash索引。hugegraph使用的是邻接表。超级点索引(vertexcentricind
菜园前端 菜园前端
10个月前
什么是图?
原文链接:什么是图?图是网络结构的抽象模型,是一组由边连接的节点。图可以表示任何二元关系,比如道路、航班等。在JavaScript中没有图,但是可以通过Object和Array来构建图。常用操作深度优先遍历广度优先遍历图的表示法邻接矩阵邻接表关联矩阵...