Problem:


Problem A: Infected Computer

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.

Input

The input consists of multiple datasets. Each dataset has the following format:

N M

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.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the number of computers infected by the computer virus.

Sample Input

3 2
1 1 2
2 2 3
3 2
2 3 2
1 2 1
0 0

Output for the Sample Input

3
1



Sample input:
3 2
1 1 2
2 2 3
3 2
2 3 2
1 2 1
0 0


Sample output:
3
1

Submission status: Accepted

Solution code:
while 1:
	N, M = map(int,raw_input().split(" "))
	if (N, M) == (0,0):
		break
	computer = [0 for i in range(N+1)]
	computer[1] = 1
	packets =[map(int,raw_input().split(" ")) for i in range(M)]
	packets.sort()
	for t,s,d in packets:
		if computer[s] == 1:
			computer[d] = 1
	print sum(computer)

Submission status: Accepted

Solution code:
#! /usr/bin/python
# -*- coding: utf-8 -*-

while True:
    N, M = map(int, raw_input().split())
    if N == 0: break

    INF = [0]*20010
    INF[1] = 1
    p = []
    for i in range(M):
        p.append(map(int, raw_input().split()))
    p.sort()
    for t, s, d in p:
        if INF[s] == 1:
            INF[d] = 1
    print INF.count(1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 14 15:56:37 2016

"""
while True:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    
    PCs = [False] * N
    PCs[0] = True
    Packets = {}
    for _ in range(M):
        t, s, d = map(int, input().split())
        Packets[t] = (s, d)
    
    for key in sorted(Packets):
        if PCs[Packets[key][0] - 1] == True:
            PCs[Packets[key][1] - 1] = True
#            print('PC'+str(Packets[key][1])+' is infected')
            
    print(PCs.count(True))

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,input().split())
    if n+m==0:break
    a=[1]+[0]*(n-1)
    b={}
    for _ in range(m):t,s,d=map(int,input().split());b[t]=(s,d)
    for x in sorted(b):
        if a[b[x][0]-1]:a[b[x][1]-1]=1
    print(sum(a))

Submission status: Accepted

Solution code:
while True:
    N,M = map(int,input().split())
    if N == M == 0: break
    logs = []
    for i in range(M):
        t,s,d = map(int,input().split())
        s,d = s-1,d-1
        logs.append((t,s,d))
    infected = [0 for i in range(N)]
    infected[0] = 1
    for t,s,d in sorted(logs):
        if infected[s]:
            infected[d] = 1
    print(sum(infected))

Submission status: Accepted

Solution code:
while True:
    n, m = map(int, input().split())
    if n == m == 0:
        break

    data = [list(map(int, input().split())) for i in range(m)]

    data.sort()
    infect = [False for i in range(n + 1)]
    infect[1] = True
    for t, s, d in data:
        if infect[s]:
            infect[d] = True

    print(infect.count(True))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,m = LI()
        if n == 0 and m == 0:
            break
        a = [LI() for _ in range(m)]
        a.sort()
        u = set([1])
        for t,s,d in a:
            if s in u:
                u.add(d)

        rr.append(len(u))

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import sys

while True:
    N, M = map(int, sys.stdin.readline().split())
    
    if N == M == 0:
        break
    
    packet = []
    for i in xrange(M):
        packet.append(map(int, raw_input().split()))
    packet.sort()
    infected = set([1])
    for p in packet:
        if p[1] in infected:
            infected.add(p[2])
    print len(infected)

Submission status: Accepted

Solution code:
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[True]*(N+1)
    L[1]=False
    data=[map(int,raw_input().split()) for i in range(M)]
    data.sort()
    for t,s,d in data:
        if L[s]==False:
            L[d]=False
    print L.count(False)

Submission status: Accepted

Solution code:
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	tsd = sorted([map(int,raw_input().split()) for i in range(m)])
	inf = [0]*n
	inf[0] = 1
	for t,s,d in tsd:
		if inf[s-1] == 1:
			inf[d-1] = 1
	print sum(inf)

Submission status: Accepted

Solution code:
while True:
    N, M = map(int, raw_input().split())
    if N == 0:
        break
    ls = []
    for i in range(M):
        t, s, d = map(int, raw_input().split())
        ls.append((t, s, d))
    ls.sort()
    cnt = [0, 1] + [0] * N
    for p in ls:
        cnt[p[2]] = max(cnt[p[1]], cnt[p[2]])
    print sum(cnt)