博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
1134 Vertex Cover
阅读量:5974 次
发布时间:2019-06-20

本文共 647 字,大约阅读时间需要 2 分钟。

题意:给出一个图和k个查询,每个查询给出Nv个结点,问与这些结点相关的边是否包含了整个图的所有边。

思路:首先,因为结点数较多,用邻接表存储图,并用unordered_map<int,unordered_map<int,bool>> mp;表示两个顶点的相邻关系。查询时,每读入一个结点,就删除与该结点相邻的所有邻边,若最后删除的边数恰等于图的总边数,输出Yes;否则输出No。ps.其实无需额外用vector<int> Adj[]存储图,因为unordered_map<int,unordered_map<int,bool>> mp就可以表示一个图了。

代码:

#include 
#include
#include
using namespace std;const int maxn=10005;vector
Adj[maxn];int main(){ int n,m; scanf("%d%d",&n,&m); unordered_map
> mp,tmpMp; int u,v; for(int i=0;i

 

转载于:https://www.cnblogs.com/kkmjy/p/9570831.html

你可能感兴趣的文章
CentOS 6.x 快速安装L2TP ***
查看>>
mysql主主复制(双主复制)配置步骤
查看>>
一篇文章能够看懂基础源代码之JAVA篇
查看>>
什么是大数据技术架构
查看>>
【分享】如何救援記憶卡中誤刪的資料
查看>>
北方计算机专修学院“展示自我 秀出风采” 网页创意设计大赛成功举办
查看>>
DNS解析相关实验:7台主机的恩怨情仇
查看>>
Goldengate双向复制配置
查看>>
Oracle官方内部MAA教程
查看>>
DNS相关配置
查看>>
Nginx-location配置
查看>>
扫描线
查看>>
设计模式--模板方法(Template Method)
查看>>
引入CSS的方式有哪些?link和@import的有何区别应如何选择【转载】
查看>>
MariaDB 和 MySQL 性能测试比较
查看>>
Restful Web Service初识
查看>>
This用法和闭包
查看>>
JSP页面获取系统时间
查看>>
L-1-19 Linux之RAID&分区&文件系统命令
查看>>
stat查找权限以数字形式显示
查看>>