2589. Infected Computer

单点时限: 2.0 sec

内存限制: 256 MB

Adam Ivan is working as a system administrator at Soy Group, Inc. He is now facing at a big trouble:a number of computers under his management have been infected by a computer virus. Unfortunately,anti-virus system in his company failed to detect this virus because it was very new.

Adam has identified the first computer infected by the virus and collected the records of all data packets sent within his network. He is now trying to identify which computers have been infected. A computer is infected when receiving any data packet from any infected computer. The computer is not infected, on the other hand, just by sending data packets to infected computers.

It seems almost impossible for him to list all infected computers by hand, because the size of the packet records is fairly large. So he asked you for help: write a program that can identify infected computers.


The input has the following format:


t1 s1 d1

t2 s2 d2

. . .

tM sM dM

N is the number of computers; M is the number of data packets; ti (1 ≤ i ≤ M) is the time when the i-th data packet is sent; si and di (1 ≤ i ≤ M) are the source and destination computers of the i-th data packet respectively. The first infected computer is indicated by the number 1; the other computers are indicated by unique numbers between 2 and N.

The input meets the following constraints: 0 < N ≤ 20000, 0 ≤ M ≤ 20000, and 0 ≤ ti ≤ 109 for 1 ≤ i ≤ N; all ti’s are different; and the source and destination of each packet are always different.


Print the number of computers infected by the computer virus.


3 2
1 1 2
2 2 3
3 2
2 3 2
1 2 1

33 人解决,53 人已尝试。

46 份提交通过,共有 171 份提交。

5.0 EMB 奖励。

创建: 10 年,8 月前.

修改: 3 年,4 月前.

最后提交: 7 月,2 周前.

来源: Japan