现在小孩的竞赛题目难了。

图论的题目要拿到分，除了拿下模板至少还要做两件事：

1，要搞清楚算法为什么正确，就是要看正确性证明。
   这个大部分培训班都不讲，给的理由是不考证明。
   但是，不看证明，遇到需要魔改算法的时候，要么胡来，要么不敢动。
   只有你知道原理，知道正确性从何而来，才敢自己改轮子。
  -- 举个例子，比如有些题目，松弛操作从松弛最短路，到松弛路径上最大边权。
   这个能不能做？为什么是对的？
   如果你知道 Floyd 算法的本质是动态规划，就很自然能想到做法。

2，要练习建图
   图论的难题往往是看不出有图，或者，不敢魔改建图。
   比如去年 Noi Online 的《重力球》，能不能从题面看出来是图论呢？
   建图是另外的功夫，主要靠直觉，也有些窍门。本质上也考察对算法原理的深刻理解。


我来贴道题，看得出来是图论吗？

猪场的朋友圈
==================

二师兄勤工俭学，去一家养猪场做算法研究。

最开始养猪场有 N 头猪，他们之间有 M 对相互认识的关系(1≤N,M≤3000)。二师兄专门负责研究这些猪的社交关系。

如果猪场所有的猪之间可以通过朋友圈互相认识（包括直接认识和间接认识），二师兄就记录下一个 "YES"，否则就记录 "NO"。

每天上午，会有一头最优秀的猪代表大伙儿去食堂参加活动，并且不再回来。二师兄就需要重新统计它们之间的社交关系，直到所有的猪都去参加活动。

#### 输入格式:

第一行包含两个整数 N 和 M，分别代表猪的数量和猪之间相互认识的关系数量。

紧接着 M 行，每行两个整数 A 和 B，代表 A 和 B 互相认识。猪的编号为 1 ... N。

再接着 N 行，每行一个整数，是依次去参加活动的编号。

#### 输出格式:

输出 N 行，每行包含 “YES” 或者 “NO”。表示猪场剩下的猪之间是否相互认识。

第一行为二师兄刚到时猪群的社交情况，接下来每一行为送走一头猪之后的社交情况。










【 在 jercy 的大作中提到: 】
: 图论需要学这些？我看他们也就是背背模板
: 发自「今日水木 on V2055A」
--
修改:ameng FROM 61.135.255.*
FROM 61.135.255.*

绝对不止，初二孩子高手已经很多了，我们福建有六年级拿提高一的
【 在 ameng 的大作中提到: 】
: 才初二啊？  
: 我一直以为您家娃已经上初三了呢。  
:  
: 如果只看初二以下的北京选手，能拿下 NOIP 两题的，有三个吗？  
:  
: --

发自「今日水木 on V2055A」
--
FROM 27.149.92.*

现在感觉是越来越难了，水涨船高

【 在 ameng (阿萌) 的大作中提到: 】
: 现在小孩的竞赛题目难了。
: 图论的题目要拿到分，除了拿下模板至少还要做两件事：
: 1，要搞清楚算法为什么正确，就是要看正确性证明。
: ...................
--
FROM 210.12.183.*

这个二师兄题目不错，你自己想的题？有输入输出样例吗？
【 在 ameng 的大作中提到: 】
: 现在小孩的竞赛题目难了。图论的题目要拿到分，除了拿下模板至少还要做两件事：1，要搞清楚算法为什么正确，就是要看正确性证明 ...
--
FROM 219.237.184.*

noip两道题已经很牛了啊~
--
FROM 202.106.10.*