Time Limit: 3 Seconds Memory Limit: 65536 KB
Edward is a rich man. He owns a large factory for health drink production. As a matter of course, there is a large warehouse in the factory.
To ensure the safety of drinks, Edward hired a security man to patrol the warehouse. The warehouse has N piles of drinks and M passageways connected them (warehouse is not big enough). When the evening comes, the security man will start to patrol the warehouse following a path to check all piles of drinks.
Unfortunately, Edward is a suspicious man, so he sets sensors on K piles of the drinks. When the security man comes to check the drinks, the sensor will record a message. Because of the memory limit, the sensors can only record for the first time of the security man's visit.
After a peaceful evening, Edward gathered all messages ordered by recording time. He wants to know whether is possible that the security man has checked all piles of drinks. Can you help him?
The security man may start to patrol at any piles of drinks. It is guaranteed that the sensors work properly. However, Edward thinks the security man may not works as expected. For example, he may digs through walls, climb over piles, use some black magic to teleport to anywhere and so on.
Input
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
The first line contains three integers N (1 <= N <= 100000), M (1 <= M <= 200000) and K (1 <= K <= N).
The next line contains K distinct integers indicating the indexes of piles (1-based) that have sensors installed. The following M lines, each line contains two integers Ai and Bi (1 <= Ai, Bi <= N) which indicates a bidirectional passageway connects piles Ai and Bi.
Then, there is an integer L (1 <= L <= K) indicating the number of messages gathered from all sensors. The next line contains L distinct integers. These are the indexes of piles where the messages came from (each is among the K integers above), ordered by recording time.
Output
For each test case, output "Yes" if the security man worked normally and has checked all piles of drinks, or "No" if not.
Sample Input
2 5 5 3 1 2 4 1 2 2 3 3 1 1 4 4 5 3 4 2 1 5 5 3 1 2 4 1 2 2 3 3 1 1 4 4 5 3 4 1 2
Sample Output
No Yes
题意:
给出 N(1 ~ 100000),M(2 ~ 200000),K(1 ~ N),代表有 N 个结点,M 条边,K 个传感器。后给出 M 条双向边,给出一个 L 长度的序列,代表要求传感器发生记录的顺序。传感器只会记录第一次记录的时间,问可不可能遍历完所有结点且存在 L 这样的顺序。
思路:
DFS。首先要弄清楚,走过的点可以重复走,所以比如存在 3,4,2,1 这样的序列,3 要到达 4 且不经过后面任何一个传感器(就是 2 和 1 ),接下来如果走到 2 到 1 的话,前面的传感器对他们是没有任何要求的,如果 3 或者 4 能够到达 1 这个结点的话,说明 2 可以通过 3 或者 4 结点到达 1 这个结点。所以每次 DFS 都是从一个传感器开始到另一个传感器结束,每次 DFS 之前先判断这个传感器是否已经被达到过了,如果不曾达到过的话,说明之前所有的点都到不了这个点,这时候就可以直接跳出循环了;如果达到过的话,就继续 DFS,以这个传感器为起点,直到找到新的另一个传感器。最后还有记得判断是否为连通图,可以直接依赖 vis 函数来判断是否连通,连通的话,应该所有结点的 vis 都为 true。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int VMAX = 100005; vector<int> G[VMAX]; int aim[VMAX]; bool vis[VMAX], sen[VMAX]; void dfs (int x) { for (int i = 0; i < G[x].size(); ++i) { int v = G[x][i]; if (!vis[v]) { vis[v] = 1; if (!sen[v]) dfs(v); } } } int main() { int t; scanf("%d", &t); while (t--) { int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; ++i) { G[i].clear(); vis[i] = sen[i] = 0; } for (int i = 0; i < k; ++i) { int x; scanf("%d", &x); sen[x] = 1; } while (m--) { int a, b; scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); } int l; scanf("%d", &l); for (int i = 1; i <= l; ++i) { scanf("%d", &aim[i]); } if (l < k) printf("No\n"); else { int temp = 0; vis[ aim[1] ] = 1; for (int i = 1; i <= l; ++i) { if (!vis[ aim[i] ]) { temp = 1; break; } dfs(aim[i]); sen[ aim[i] ] = 0; } for (int i = 1; i <= n; ++i) { if (!vis[i]) { temp = 1; break; } } if (!temp) printf("Yes\n"); else printf("No\n"); } } return 0; }
相关推荐
zoj 3811 Untrusted Patrol.md
Zero Trust Networks Building Secure Systems in Untrusted Networks 英文epub 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书
SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud NIPS2017会议论文
NULL 博文链接:https://ocaicai.iteye.com/blog/1764678
Zero Trust Networks Building Secure Systems in Untrusted Networks
Untrusted-RU / 手册 将 Untrusted 游戏在线手册 ( ) 翻译成俄语 请注意:Untrusted 目前仅提供英文版本。 此翻译是开始游戏本身本地化之前的准备阶段。 去做 完成翻译:) 测试版(修复错误) 修复元标记 修复...
MIT的Paper 雲端安全新趨勢 利用編碼技術達成資訊不足的的安全性
Zero Trust Networks :Building Secure Systems in Untrusted Networks from Evan Gilman and Doug Barth,零信任网络:在不信任的网络中穿件安全的系统
下面小编就为大家带来一篇完美解决node.js中使用https请求报CERT_UNTRUSTED的问题。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
DevTools的不受信任类型 不受信任的类型是Chrome扩展程序,它滥用来记录DOMXSS接收器。 安装 使用npm 克隆存储库 安装依赖项: npm i 生成项目: npm run build 转到chrome://extensions ,启用开发人员模式 ...
安卓12卡触摸解决教程.zip
web application security, 2010
语言:English 滥用可信类型来发现XSS接收器。 发现并测试传递到接收器中的输入,这些输入接收器可能会导致DOM XSS漏洞。 接收器是一种代码模式,如果输入是恶意的,则可以运行任意JavaScript代码,例如:innerHTML,...
可靠地从不受信任的来源中学习 介绍 该git存储库包含ICML 2019论文用于实验的代码。 尤其是所用的功能,用于运行大型实验的脚本以及用于从纸上创建绘图和表格的Jupyter Notebooks(包括在内)。...
不可信级别 20-boss-fight-awesome-solution Untrusted Level 20 Boss Fight的一个非常棒的解决方案 - 将代码复制到关卡中进行检查!
Security-aware task scheduling using untrusted components in high-level synthesis
3GPP 技术文档 36300-a00 第四章-Overall architecture 第五章-Physical Layer for E-UTRA 第六章-Layer 2 第七章-RRC ......
*pdwSupportedOptions = INTERFACESAFE_FOR_UNTRUSTED_CALLER; *pdwEnabledOptions = m_dwSafety & INTERFACESAFE_FOR_UNTRUSTED_CALLER; return S_OK; }else if ((riid == IID_IPersistStreamInit) || (riid == IID...