| 题目名称 | 449. 网络病毒 |
|---|---|
| 输入输出 | virus.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Pom
于2010-06-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：58， 提交：157， 通过率：36.94% | ||||
 Bennettz |
100 | 0.046 s | 8.29 MiB | C++ |
 AAAAAAAAAA |
100 | 0.058 s | 8.15 MiB | C++ |
 Hyoi_0Koto |
100 | 0.063 s | 2.49 MiB | C++ |
 yuan |
100 | 0.088 s | 6.60 MiB | C++ |
 0 |
100 | 0.114 s | 25.35 MiB | C++ |
 Fancy、 |
100 | 0.115 s | 4.15 MiB | C++ |
 皓芷 |
100 | 0.125 s | 0.40 MiB | C++ |
 雨季 |
100 | 0.186 s | 7.24 MiB | C++ |
|
dsn |
100 | 0.222 s | 2.25 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.228 s | 8.03 MiB | C++ |
| 关于 网络病毒 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
芜湖
| ||||
|
塔尖儿模板题
AAAAAAAAAA
2017-10-31 09:29
8楼
| ||||
|
好久没写tarjan啦。求入度为零的强连通分量的个数。
| ||||
|
回复 @皓芷 :
你想挑起卡常战争么？（恶意互评禁止） Hyoi_0Koto
2017-10-07 15:18
6楼
| ||||
|
话说cogs tab键真长。。。好丑。。。
皓芷
2017-09-29 08:17
5楼
| ||||
|
回复 @Hyoi_0Koto :
哦？是嘛。（滑稽）kosaraju大法好 | ||||
|
回复 @Regnig Etalsnart :
所以你没tarjan跑得快（滑稽） Hyoi_0Koto
2017-09-28 16:51
3楼
| ||||
|
我只会kosaraju大法好
| ||||
|
有一个点不知道怎么错了。。。
| ||||
Shirry
Regnig Etalsnart
【题目描述】
公元2008年10月31日星期五，笃志者所在的整个机房由于猖獗的病毒一片恐慌。经查证，病毒是由A1机器散播开来的。。这要追溯到29日，笃志者由于病毒被迫从A1机器撤离。
一想到病毒是从自己的机器传开的，笃志者就心神不宁。他决定搞清楚病毒是怎么散播开来的。事实上，机房内的机器并不是全部都能够互相感染的。笃志者（ceeji）好不容易经过测试得到了机房中各机器间是否连通的图表，就在他马上就要得出结果的时候，大脑突然乱了！问题的严重性在于：如果他不在1s内搞清楚这个问题，机房就会整体瘫痪。现在笃志者求助于你，他需要知道病毒从未感染机房开始，最少入侵几台机器之后，机房就会整体感染。
【输入格式】
文件的第一行为一个整数n，第二行至第n+1行为n*n的矩阵（若第i行第j列为1，则机器i能对机器j进行ARP攻击（即感染机器j），若第i行第j列为0，则机器i不能感染机器j）。
【输出格式】
输出文件只有一行，为笃志者想知道的最少感染机器数。
【输入样例】
8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0
【输出样例】
2
【数据范围】
对于 100% 的数据，n<=1000；