当前位置: 首页 > news >正文

VK Cup 2017 - Round 1 A - Bear and Friendship Condition(并查集维护大小 + dfs 遍历图统计边数)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

题目大意:

给你一些n个点m条边,如果三个点(a,b,c)是合法的,当且仅当 a-b,b-c,c-a都有一条边,问你这个图是否合法,如果有一个或两个点视为合法

思路

考虑什么图才是个合法图:除了点数小于 3 的图一定合法外,必须是完全图才合法,假设完全图有 n 个点,则它的边数为:(n - 1) * n / 2。

用并查集分割为若干个集合,dfs 遍历每个集合,判断每个大小大于2的图是否是完全图即可。

这里积累个小技巧,用set存图,每次操作 logn,方便统计图的边数,具体看代码。

时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)

代码:

#include<bits/stdc++.h>using namespace std;
#define int long long
const int N = 1.5e5 + 10;
int n, m;
int p[N], siz[N];
set<int> g[N];
int edge = 0;
bool vis[N];int Find(int x) {if (p[x] != x) {p[x] = Find(p[x]);}return p[x];
}void dfs(int u)
{vis[u] = true;edge += g[u].size();for (auto son : g[u]) {g[son].erase(u);}for (auto son : g[u]) {if (vis[son]) continue;dfs(son);}
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; ++i) {p[i] = i;siz[i] = 1;}for (int i = 0; i < m; ++i) {int a, b; cin >> a >> b;g[a].insert(b);g[b].insert(a);int pa = Find(a), pb = Find(b);if (pa != pb) {siz[pb] += siz[pa];p[pa] = pb;}}for (int i = 1; i <= n; ++i) {p[i] = Find(i);}for (int i = 1; i <= n; ++i) {if (p[i] != i || siz[i] <= 2) continue;edge = 0;dfs(i);if (edge != siz[i] * (siz[i] - 1) / 2) {cout << "NO" << '\n';return 0;}}cout << "YES" << '\n';return 0;
}
http://www.lryc.cn/news/65628.html

相关文章:

  • 为UOS启用VNC和Windows远程桌面
  • Java时间类(七)-- LocalDateTime()类
  • 卢北辰:数据点亮梦想,能力驱动人生 | 提升之路系列(九)
  • 数据库基础及用户管理授权
  • 比特米盒子刷安卓ATV6.0
  • 【用python的QT做信号处理的界面】
  • 【Linux】进程间通信 —— 管道
  • 知识管理在企业中的重要性
  • Socks5、网络安全、代理IP技术详解
  • C++学习day--09 字符串比较、运算符
  • 缓存和数据库一致性问题
  • 4月京东生鲜水果行业数据报告:榴莲销量增长400%,市场格局剧变
  • Windows无法完成格式化怎么办?正确的3个解决方法!
  • 基于aspnet个人博客网站dzkf6606程序
  • 不黑艺术学社京藏行——参观五台山孙溟㠭为五台山红英师治印
  • mysql数据之表管理-mysql高级管理
  • 公司新来的00后真是卷王,工作没2年,跳槽到我们公司起薪18K都快接近我了
  • 面试题30天打卡-day19
  • ASEMI代理ADI亚德诺LTC6992IS6-1#TRMPBF车规级芯片
  • Oracle PL/SQL基础语法学习15:静态表达式
  • B-Tree (多路查找树)分析-20230503
  • OpenGL光照教程之 透光物
  • 如何使用hook?
  • 双指针技巧秒杀七道链表题目
  • 在“裸奔”时代保护我们的隐私:网络攻击、数据泄露与隐私侵犯的应对策略与工具
  • 如何写出高质量代码
  • [oeasy]python0048_注释_comment_设置默认编码格式
  • C++中的queue与priority_queue
  • 电脑发挥极致,畅游永恒之塔sf
  • ChatGPT :十几个国内免费可用 ChatGPT 网页版