Codeforces542E Playing on Graph 思维+DFS+BFS
2024-09-06 03:55:23
解法参考https://www.cnblogs.com/BearChild/p/7683114.html这位大佬的,这位大佬讲得很好了。
这道题还是有一定的思维的。
直接贴代码:
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=+;
const int M=+;
int n,m,ecc_cnt,ans,color[N],Max[N],ecc[N];
vector<int> G[N];
bool ok; void dfs(int x,int c) {
color[x]=c; ecc[x]=ecc_cnt;
for (int i=;i<G[x].size();i++) {
int y=G[x][i];
if (color[y]==color[x]) ok=false;
if (!color[y]) dfs(y,-c);
}
} queue<int> q;
int d[N];
int bfs(int s) {
while (!q.empty()) q.pop();
memset(d,,sizeof(d));
d[s]=; q.push(s);
int res=;
while (!q.empty()) {
int x=q.front(); q.pop();
for (int i=;i<G[x].size();i++) {
int y=G[x][i];
if (!d[y]) {
d[y]=d[x]+;
res=max(res,d[y]);
q.push(y);
}
}
}
return res;
} int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++) {
int x,y; scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
} ecc_cnt=; ok=true;
for (int i=;i<=n;i++)
if (!ecc[i]) {
ecc_cnt++;
dfs(i,);
}
if (!ok) { puts("-1"); return ; } for (int i=;i<=n;i++)
Max[ecc[i]]=max(Max[ecc[i]],bfs(i));
for (int i=;i<=ecc_cnt;i++) ans+=Max[i]-;
cout<<ans;
return ;
}
最新文章
- ZKWeb网页框架1.3正式发布
- Windows10自适应和交互式toast通知[1]
- 微软要如何击败Salesforce?Office365、Azure、Dynamics365 全面布局AI | 双语
- 微信公众平台API接口
- js地区转盘抽奖插件
- C# 生成随机数
- mysql-python模块编译问题解决
- Codeforces Gym 100231B Intervals 线段树+二分+贪心
- CF GYM 100703M It&#39;s complicate
- MVC模式 - 理解J2EE模式
- Oracle基于学习3--Oracle创建用户和授权
- 转:JSP 分页显示数据 (Oracle)
- Two-phase clustering process for outliers detection 文章翻译
- mysql进阶(十一)外键在数据库中的作用
- unittest报告出现dict() ->; new empty dictionary错误解决办法
- The component and implementation of a basic gradient descent in python
- JS 模拟 重载
- Python官方操作Excel文档
- .NetCore下使用Prometheus实现系统监控和警报 (六)进阶Grafana集成自定义收集指标
- 微信小程序无法获取UnionId的情况及处理