Codeforces 862B (二分图染色)

Stella981
• 阅读 839

<题目链接>

题目大意:

给出一个有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

点赞
收藏
评论区
推荐文章
Stella981 Stella981
3年前
Python绘制拓扑图(无向图)、有向图、多重图。最短路径计算
前言:数学中,“图论”研究的是定点和边组成的图形。计算机中,“网络拓扑”是数学概念中“图”的一个子集。因此,计算机网络拓扑图也可以由节点(即顶点)和链路(即边)来进行定义和绘制。延伸:无向图两个节点之间只有一条线相连接,且没有方向。 有向图两个节点之间只有一条线相连接,且有方向。方向可以单向,也可以双向。 多重图两个节点之
Stella981 Stella981
3年前
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
3年前
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
3年前
LeetCode 5561. 获取生成数组中的最大值
文章目录1\.题目2\.解题1\.题目给你一个整数n。按下述规则生成一个长度为n1的数组nums:nums00nums11当2<2i<n时,nums2inumsi
Stella981 Stella981
3年前
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
3年前
Graph Coarsening And multi
Coarsening\何慧,胡铭曾,张宏莉,裴晓峰,&杨志.(2005).网络拓扑图多级分割塌缩阶段算法改进.华中科技大学学报:自然科学版,33(S1),8285.\图塌缩阶段是将图中联系较强部分粘合起来作为一个整体,并暂时从图中隐藏掉.这样经过多次塌缩后,使图变小.例如一个复杂的数千条边的图会经塌缩阶
贾蔷 贾蔷
3天前
牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)
一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n1条边构成,保证为连通无环图。理解题目核心在于准确获取树的拓扑关系,并设计算法遍历
菜园前端 菜园前端
2年前
什么是图?
原文链接:什么是图?图是网络结构的抽象模型,是一组由边连接的节点。图可以表示任何二元关系,比如道路、航班等。在JavaScript中没有图,但是可以通过Object和Array来构建图。常用操作深度优先遍历广度优先遍历图的表示法邻接矩阵邻接表关联矩阵...
贾蔷 贾蔷
3天前
邻接表实现指南:图结构的链表存储方式
一、简介和特点邻接表是一种常用的图存储结构,它使用链表来表示图中顶点之间的邻接关系。本文实现的邻接表类可以高效地表示稀疏图,并支持动态添加顶点和边。‌主要特点‌:空间效率:特别适合存储稀疏图动态扩展:可以灵活添加顶点和边直观表示:直接反映图的连接关系权重支
深度学习 深度学习
3天前
洛谷1111题解:基于Kruskal算法与并查集的最小生成树实现
一、题目解读洛谷1111题是一道经典的图论问题,要求构建一个无向图的最小生成树,并输出其最大边权值。题目核心在于通过给定的边集合,找到连接所有节点的最小权值子集,同时保证无环。这通常涉及最小生成树算法(如Kruskal)的应用,需要高效处理边权重与节点连通