{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n\t#problem-ul-reset{\r\n\t\tlist-style-position: inside;\r\n \t\tlist-style-type: decimal;\r\n\t \tmargin: 15px;\r\n\t}\r\n\t#problem-ul-reset li{ margin:5px 0; }\r\n\u003c/style\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e 小Hi和小Ho所在学校的校园网被黑客入侵并投放了病毒。这事在校内BBS上立刻引起了大家的讨论,当然小Hi和小Ho也参与到了其中。从大家各自了解的情况中,小Hi和小Ho整理得到了以下的信息:\u003c/p\u003e \n \u003cul id\u003d\"problem-ul-reset\"\u003e \n \u003cli\u003e校园网主干是由N个节点(编号1..N)组成,这些节点之间有一些单向的网路连接。若存在一条网路连接(u,v)链接了节点u和节点v,则节点u可以向节点v发送信息,但是节点v不能通过该链接向节点u发送信息。\u003c/li\u003e \n \u003cli\u003e在刚感染病毒时,校园网立刻切断了一些网络链接,恰好使得剩下网络连接不存在环,避免了节点被反复感染。也就是说从节点i扩散出的病毒,一定不会再回到节点i。\u003c/li\u003e \n \u003cli\u003e当1个病毒感染了节点后,它并不会检查这个节点是否被感染,而是直接将自身的拷贝向所有邻居节点发送,它自身则会留在当前节点。所以一个节点有可能存在多个病毒。\u003c/li\u003e \n \u003cli\u003e现在已经知道黑客在一开始在K个节点上分别投放了一个病毒。\u003c/li\u003e \n \u003c/ul\u003e \n \u003cp\u003e 举个例子,假设切断部分网络连接后学校网络如下图所示,由4个节点和4条链接构成。最开始只有节点1上有病毒。\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/a759cb324caff4340e3177f952cbf970?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_1.png\"\u003e\u003c/p\u003e \n \u003cp\u003e最开始节点1向节点2和节点3传送了病毒,自身留有1个病毒:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/1dde40117da969f0fce396e9f78f469e?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_2.png\"\u003e\u003c/p\u003e \n \u003cp\u003e其中一个病毒到达节点2后,向节点3传送了一个病毒。另一个到达节点3的病毒向节点4发送自己的拷贝:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/db052b5d29941d54e35faed5ced81c87?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_3.png\"\u003e\u003c/p\u003e \n \u003cp\u003e当从节点2传送到节点3的病毒到达之后,该病毒又发送了一份自己的拷贝向节点4。此时节点3上留有2个病毒:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/9b713c75c8da1ba42dc1723a5c9829b4?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_4.png\"\u003e\u003c/p\u003e \n \u003cp\u003e最后每个节点上的病毒为:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/4959588ad4b3a29009e53c4df41d750f?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_5.png\"\u003e\u003c/p\u003e \n \u003cp\u003e小Hi和小Ho根据目前的情况发现一段时间之后,所有的节点病毒数量一定不会再发生变化。那么对于整个网络来说,最后会有多少个病毒呢? \u003c/p\u003e \u003c!-- Button trigger modal --\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:拓扑排序的应用\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:拓扑排序的应用\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:对于这个问题小Ho你有什么想法么?\u003c/p\u003e \n \u003cp\u003e小Ho:有,对于一个病毒来说它总会传递到一个没有邻居的节点,那我直接使用dfs模拟整个过程不就能够得到结果了吗?\u003c/p\u003e \n \u003cp\u003e小Hi:小Ho你真聪明,立刻就看穿了这个问题的本质。\u003c/p\u003e \n \u003cp\u003e小Ho:那当然啦。\u0026lt;得意\u0026gt;\u003c/p\u003e \n \u003cp\u003e小Hi:那么小Ho,我这里有这样一个网络:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/0f69f8224c32c93818f1eab7ba59b100?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_6.png\"\u003e\u003c/p\u003e \n \u003cp\u003e这里一共有n个节点,对于节点i,它总是连接着节点i+1和节点i+2。一开始只有节点1被感染,你算算最后n个节点一共有多少个病毒?\u003c/p\u003e \n \u003cp\u003e小Ho:很显然,节点1最后只有1个病毒;节点2也只有1个病毒;节点3会接受从节点1和节点2过来的病毒,所以有2个病毒;后面依次是节点4有3个病毒,节点5有5个病毒…它们好像刚好是费波拉契数列?\u003c/p\u003e \n \u003cp\u003e小Hi:你说的没错。对于这个网络,编号为i的节点最后感染的病毒数量就是斐波拉契数列的第i项。而斐波拉契数列的增长是很惊人的,当i到达一定值时,其电脑感染的病毒数量就会很大了。\u003c/p\u003e \n \u003cp\u003e小Ho:那这又有什么关系呢?反正能得到解不是么?\u003c/p\u003e \n \u003cp\u003e小Hi:能得到解那是当然了,但是你有想过需要花费多少时间么?在你的dfs算法中,每一次进入函数就等于模拟一个病毒进入电脑。如果最后结果有10亿个病毒,那么你就需要执行10亿次函数,假设电脑每秒钟可以执行1亿次函数,那么你的dfs就需要运行10秒。如果结果有100亿,1000亿呢?\u003c/p\u003e \n \u003cp\u003e小Ho:运行时间上好像是有问题,那我应该如何解决时间的问题呢?\u003c/p\u003e \n \u003cp\u003e小Hi:其实也很简单啦。你再想想,在我们最后得到结果上每各节点病毒数量有什么关系么?\u003c/p\u003e \n \u003cp\u003e小Ho:嗯\u0026lt;思考\u0026gt;…我发现了!对于节点i来说,它最后的病毒数好像总是等于所有能够达到它的节点病毒数之和。就用你提到的那个斐波拉契数列来说,能够达到节点i的节点是节点i-1和节点i-2,所以节点i的病毒数是节点i-1和节点i-2的病毒数之和。这刚好就是斐波拉契数列的递推公式嘛!\u003c/p\u003e \n \u003cp\u003e小Hi:对,正是这样。对于一个节点i来说,如果我们能够先计算出它所有前驱节点的病毒数量,就可以直接推算出它最后的病毒数量了。\u003c/p\u003e \n \u003cp\u003e小Ho:但是怎么来计算所有前驱节点呢?\u003c/p\u003e \n \u003cp\u003e小Hi:这就要从图的性质入手了。我们现在的网络是没有环的,对于任意一个节点i,当它将自己所有的病毒都传送出去之后,它自身的病毒数量就不会改变了。那么我们不妨从没有前驱节点,也就是入度为0的节点开始考虑。\u003c/p\u003e \n \u003cp\u003e对于这些节点,它并不会再增加病毒数量。那么我们就根据它所关联的连接将病毒分发出去,然后这个节点就没有作用了。那不妨就删掉好了,它所关联的边也删掉。\u003c/p\u003e \n \u003cp\u003e这样图中又会产生一些新的没有入度的节点。这样一直删点,直到所有的点都被删掉,将所有点的病毒数量加起来不就是总的病毒数么?\u003c/p\u003e \n \u003cp\u003e我们不妨来看个例子,这里给定一个网络:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/a759cb324caff4340e3177f952cbf970?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_1.png\"\u003e\u003c/p\u003e \n \u003cp\u003e最开始只有节点1是入度为0的点,所以将它的病毒传送,然后删掉节点1:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/f661d8f9b513f8e0c87383f0c7abd68e?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_7.png\"\u003e\u003c/p\u003e \n \u003cp\u003e此时节点2成为了入度为0的点,同样将其删掉:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/4d3680148b112fd6a6a0208bbbc3e5dd?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_8.png\"\u003e\u003c/p\u003e \n \u003cp\u003e此时节点3为入度为0的点,同样操作:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/87785a2e99b837431c9e5cb7ace6dafa?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_9.png\"\u003e\u003c/p\u003e \n \u003cp\u003e最后只剩下节点4,因为它并没有后续节点,所以病毒感染的过程也就结束了。\u003c/p\u003e \n \u003cp\u003e小Ho:这不就是拓扑排序么!因为拓扑排序可以在O(n+m)的时间解决,整个问题的时间也减少到了O(n+m),那么再多的节点数都不怕了!\u003c/p\u003e \n \u003cp\u003e小Hi:没错,这样我们就完美地解决了这个问题。你能实现它么?\u003c/p\u003e \n \u003cp\u003e小Ho:没问题,就交给我吧!\u0026lt;自信\u0026gt;\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:3个整数N,M,K,1≤K≤N≤100,000,1≤M≤500,000\u003c/p\u003e \n \u003cp\u003e第2行:K个整数A[i],A[i]表示黑客在节点A[i]上放了1个病毒。1≤A[i]≤N\u003c/p\u003e \n \u003cp\u003e第3..M+2行:每行2个整数 u,v,表示存在一条从节点u到节点v的网络链接。数据保证为无环图。1≤u,v≤N\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e第1行:1个整数,表示最后整个网络的病毒数量 MOD 142857\u003c/p\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e4 4 1\r\n1\r\n1 2\r\n1 3\r\n2 3\r\n3 4\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e6\u003c/pre\u003e \n\u003c/dd\u003e\n\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n\t#problem-ul-reset{\r\n\t\tlist-style-position: inside;\r\n \t\tlist-style-type: decimal;\r\n\t \tmargin: 15px;\r\n\t}\r\n\t#problem-ul-reset li{ margin:5px 0; }\r\n\u003c/style\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e 小Hi和小Ho所在学校的校园网被黑客入侵并投放了病毒。这事在校内BBS上立刻引起了大家的讨论,当然小Hi和小Ho也参与到了其中。从大家各自了解的情况中,小Hi和小Ho整理得到了以下的信息:\u003c/p\u003e \n \u003cul id\u003d\"problem-ul-reset\"\u003e \n \u003cli\u003e校园网主干是由N个节点(编号1..N)组成,这些节点之间有一些单向的网路连接。若存在一条网路连接(u,v)链接了节点u和节点v,则节点u可以向节点v发送信息,但是节点v不能通过该链接向节点u发送信息。\u003c/li\u003e \n \u003cli\u003e在刚感染病毒时,校园网立刻切断了一些网络链接,恰好使得剩下网络连接不存在环,避免了节点被反复感染。也就是说从节点i扩散出的病毒,一定不会再回到节点i。\u003c/li\u003e \n \u003cli\u003e当1个病毒感染了节点后,它并不会检查这个节点是否被感染,而是直接将自身的拷贝向所有邻居节点发送,它自身则会留在当前节点。所以一个节点有可能存在多个病毒。\u003c/li\u003e \n \u003cli\u003e现在已经知道黑客在一开始在K个节点上分别投放了一个病毒。\u003c/li\u003e \n \u003c/ul\u003e \n \u003cp\u003e 举个例子,假设切断部分网络连接后学校网络如下图所示,由4个节点和4条链接构成。最开始只有节点1上有病毒。\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/a759cb324caff4340e3177f952cbf970?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_1.png\"\u003e\u003c/p\u003e \n \u003cp\u003e最开始节点1向节点2和节点3传送了病毒,自身留有1个病毒:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/1dde40117da969f0fce396e9f78f469e?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_2.png\"\u003e\u003c/p\u003e \n \u003cp\u003e其中一个病毒到达节点2后,向节点3传送了一个病毒。另一个到达节点3的病毒向节点4发送自己的拷贝:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/db052b5d29941d54e35faed5ced81c87?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_3.png\"\u003e\u003c/p\u003e \n \u003cp\u003e当从节点2传送到节点3的病毒到达之后,该病毒又发送了一份自己的拷贝向节点4。此时节点3上留有2个病毒:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/9b713c75c8da1ba42dc1723a5c9829b4?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_4.png\"\u003e\u003c/p\u003e \n \u003cp\u003e最后每个节点上的病毒为:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/4959588ad4b3a29009e53c4df41d750f?v\u003d1659668870\" style\u003d\"width: 60%;\" title\u003d\"week48_5.png\"\u003e\u003c/p\u003e \n \u003cp\u003e小Hi和小Ho根据目前的情况发现一段时间之后,所有的节点病毒数量一定不会再发生变化。那么对于整个网络来说,最后会有多少个病毒呢? \u003c/p\u003e \u003c!-- Button trigger modal --\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:拓扑排序的应用\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:拓扑排序的应用\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Hi:对于这个问题小Ho你有什么想法么?\u003c/p\u003e \n \u003cp\u003e小Ho:有,对于一个病毒来说它总会传递到一个没有邻居的节点,那我直接使用dfs模拟整个过程不就能够得到结果了吗?\u003c/p\u003e \n \u003cp\u003e小Hi:小Ho你真聪明,立刻就看穿了这个问题的本质。\u003c/p\u003e \n \u003cp\u003e小Ho:那当然啦。\u0026lt;得意\u0026gt;\u003c/p\u003e \n \u003cp\u003e小Hi:那么小Ho,我这里有这样一个网络:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/0f69f8224c32c93818f1eab7ba59b100?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_6.png\"\u003e\u003c/p\u003e \n \u003cp\u003e这里一共有n个节点,对于节点i,它总是连接着节点i+1和节点i+2。一开始只有节点1被感染,你算算最后n个节点一共有多少个病毒?\u003c/p\u003e \n \u003cp\u003e小Ho:很显然,节点1最后只有1个病毒;节点2也只有1个病毒;节点3会接受从节点1和节点2过来的病毒,所以有2个病毒;后面依次是节点4有3个病毒,节点5有5个病毒…它们好像刚好是费波拉契数列?\u003c/p\u003e \n \u003cp\u003e小Hi:你说的没错。对于这个网络,编号为i的节点最后感染的病毒数量就是斐波拉契数列的第i项。而斐波拉契数列的增长是很惊人的,当i到达一定值时,其电脑感染的病毒数量就会很大了。\u003c/p\u003e \n \u003cp\u003e小Ho:那这又有什么关系呢?反正能得到解不是么?\u003c/p\u003e \n \u003cp\u003e小Hi:能得到解那是当然了,但是你有想过需要花费多少时间么?在你的dfs算法中,每一次进入函数就等于模拟一个病毒进入电脑。如果最后结果有10亿个病毒,那么你就需要执行10亿次函数,假设电脑每秒钟可以执行1亿次函数,那么你的dfs就需要运行10秒。如果结果有100亿,1000亿呢?\u003c/p\u003e \n \u003cp\u003e小Ho:运行时间上好像是有问题,那我应该如何解决时间的问题呢?\u003c/p\u003e \n \u003cp\u003e小Hi:其实也很简单啦。你再想想,在我们最后得到结果上每各节点病毒数量有什么关系么?\u003c/p\u003e \n \u003cp\u003e小Ho:嗯\u0026lt;思考\u0026gt;…我发现了!对于节点i来说,它最后的病毒数好像总是等于所有能够达到它的节点病毒数之和。就用你提到的那个斐波拉契数列来说,能够达到节点i的节点是节点i-1和节点i-2,所以节点i的病毒数是节点i-1和节点i-2的病毒数之和。这刚好就是斐波拉契数列的递推公式嘛!\u003c/p\u003e \n \u003cp\u003e小Hi:对,正是这样。对于一个节点i来说,如果我们能够先计算出它所有前驱节点的病毒数量,就可以直接推算出它最后的病毒数量了。\u003c/p\u003e \n \u003cp\u003e小Ho:但是怎么来计算所有前驱节点呢?\u003c/p\u003e \n \u003cp\u003e小Hi:这就要从图的性质入手了。我们现在的网络是没有环的,对于任意一个节点i,当它将自己所有的病毒都传送出去之后,它自身的病毒数量就不会改变了。那么我们不妨从没有前驱节点,也就是入度为0的节点开始考虑。\u003c/p\u003e \n \u003cp\u003e对于这些节点,它并不会再增加病毒数量。那么我们就根据它所关联的连接将病毒分发出去,然后这个节点就没有作用了。那不妨就删掉好了,它所关联的边也删掉。\u003c/p\u003e \n \u003cp\u003e这样图中又会产生一些新的没有入度的节点。这样一直删点,直到所有的点都被删掉,将所有点的病毒数量加起来不就是总的病毒数么?\u003c/p\u003e \n \u003cp\u003e我们不妨来看个例子,这里给定一个网络:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/a759cb324caff4340e3177f952cbf970?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_1.png\"\u003e\u003c/p\u003e \n \u003cp\u003e最开始只有节点1是入度为0的点,所以将它的病毒传送,然后删掉节点1:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/f661d8f9b513f8e0c87383f0c7abd68e?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_7.png\"\u003e\u003c/p\u003e \n \u003cp\u003e此时节点2成为了入度为0的点,同样将其删掉:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/4d3680148b112fd6a6a0208bbbc3e5dd?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_8.png\"\u003e\u003c/p\u003e \n \u003cp\u003e此时节点3为入度为0的点,同样操作:\u003c/p\u003e \n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/87785a2e99b837431c9e5cb7ace6dafa?v\u003d1659668870\" style\u003d\"width: 100%;\" title\u003d\"week48_9.png\"\u003e\u003c/p\u003e \n \u003cp\u003e最后只剩下节点4,因为它并没有后续节点,所以病毒感染的过程也就结束了。\u003c/p\u003e \n \u003cp\u003e小Ho:这不就是拓扑排序么!因为拓扑排序可以在O(n+m)的时间解决,整个问题的时间也减少到了O(n+m),那么再多的节点数都不怕了!\u003c/p\u003e \n \u003cp\u003e小Hi:没错,这样我们就完美地解决了这个问题。你能实现它么?\u003c/p\u003e \n \u003cp\u003e小Ho:没问题,就交给我吧!\u0026lt;自信\u0026gt;\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:3个整数N,M,K,1≤K≤N≤100,000,1≤M≤500,000\u003c/p\u003e \n \u003cp\u003e第2行:K个整数A[i],A[i]表示黑客在节点A[i]上放了1个病毒。1≤A[i]≤N\u003c/p\u003e \n \u003cp\u003e第3..M+2行:每行2个整数 u,v,表示存在一条从节点u到节点v的网络链接。数据保证为无环图。1≤u,v≤N\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e第1行:1个整数,表示最后整个网络的病毒数量 MOD 142857\u003c/p\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e4 4 1\r\n1\r\n1 2\r\n1 3\r\n2 3\r\n3 4\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e6\u003c/pre\u003e \n\u003c/dd\u003e"}}]}