Problem:


Score : 100 points

Problem Statement

There is a directed graph G with N vertices and M edges.
The vertices are numbered 1, 2, \ldots, N, and for each i (1 \leq i \leq M), the i-th directed edge goes from Vertex x_i to y_i.
G does not contain directed cycles.

Find the length of the longest directed path in G.
Here, the length of a directed path is the number of edges in it.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq x_i, y_i \leq N

All pairs (x_i, y_i) are distinct.

G does not contain directed cycles.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the length of the longest directed path in G.

Sample Input 1

4 5
1 2
1 3
3 2
2 4
3 4

Sample Output 1

3

The red directed path in the following figure is the longest:

Sample Input 2

6 3
2 3
4 5
5 6

Sample Output 2

2

The red directed path in the following figure is the longest:

Sample Input 3

5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3

Sample Output 3

3

The red directed path in the following figure is one of the longest:



Sample input:
4 5
1 2
1 3
3 2
2 4
3 4


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

n,m=map(int,input().split())
v=[False for i in range(n)]
gr=[[] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	gr[a-1].append(b-1)
	v[b-1]=True
cnt=0
res=[0 for i in range(n)]
for i in range(n):
	if v[i]:continue
	s=[i]
	while s:
		x=s.pop()
		for j in gr[x]:
			if res[j]<res[x]+1:
				res[j]=res[x]+1
				s.append(j)
print(max(res))

Submission status: Time Limit Exceeded

Solution code:
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

n,m=map(int,input().split())
v=[False for i in range(n)]
gr=[[] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	gr[a-1].append(b-1)
	v[b-1]=True
cnt=0
res=[0 for i in range(n)]
for i in range(n):
	if v[i]:continue
	s=[i]
	while s:
		x=s.pop()
		for j in gr[x]:
			if res[j]<res[x]+1:
				res[j]=res[x]+1
				s.append(j)
print(max(res))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100001)

N, M = map(int, input().split())

dp = [0] * N
parent = [[] for _ in range(N)]
child = [False] * N

for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    parent[y].append(x)
    child[x] = True

def func(node):
    for i in parent[node]:
        if dp[i] <= dp[node]:
            dp[i] = dp[node] + 1
            func(i)

for i, b in enumerate(child):
    if not b:
        func(i)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100001)

N, M = map(int, input().split())

dp = [0] * N
parent = [[] for _ in range(N)]

def func(node):
    for i in parent[node]:
        if dp[i] <= dp[node]:
            dp[i] = dp[node] + 1
            func(i)


for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    parent[y].append(x)
    if dp[x] <= dp[y]:
        dp[x] = dp[y] + 1
        func(x)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n, m = map(int, input().split( ))
Edg = [[] for _ in range(n)]
#rev_Edg =  [[] for _ in range(n)]

Visited = [0]*n
Root_check = [1]*n
Dist = [0]*n
for i in range(m):
    v1,v2 = map(int, sys.stdin.readline().split( ))
    v1-=1
    v2-=1
    Edg[v1].append(v2)
    Root_check[v2] = 0
    
Roots = []
for i in range(n):
    if Root_check[i] == 1:
        Roots.append(i)
Q =deque()
for r in Roots:
    Q.append(r)
    while len(Q) > 0:
        v = Q.popleft()
        for w in Edg[v]:
            Dist[w] = max(Dist[w],Dist[v] +1)####
            Q.append(w)

print(max(Dist))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split( ))
Edg = [[] for _ in range(n)]

Root_check = [1]*n
Dist = [0]*n
for i in range(m):
    v1,v2 = map(int, input().split( ))
    v1-=1
    v2-=1
    Edg[v1].append(v2)
    Root_check[v2] = 0
    
Roots = []
for i in range(n):
    if Root_check[i] == 1:
        Roots.append(i)
Q = deque()
for r in Roots:
    Q.append(r)
    while len(Q) > 0:
        v = Q.popleft()
        for w in Edg[v]:
            Dist[w] = max(Dist[w],Dist[v] +1)####
            Q.append(w)

print(max(Dist))

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split()]
edges = [[0 for i in range(N)] for j in range(N+1)]
for i in range(M):
    x, y = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    edges[x][y] = 1
for i in range(N):
    edges[N][i] = 1

memo_ls = [None for i in range(N+1)]
def dfs(last):
    if memo_ls[last] is not None:
        return memo_ls[last]
    cnt = max([dfs(next) + 1 if edges[last][next] != 0 else 0 for next in range(N)])
    memo_ls[last] = cnt
    return cnt
print(dfs(N) - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

from functools import lru_cache


def main():
    N, M = LI()
    es = [[x for x in LI()] for _ in range(M)]

    from collections import defaultdict
    outs = defaultdict(list)  # ノードが int なら、[[] for _ in range(n+1)] でもよさそう。
    # ins = defaultdict(int)    # ノードが int なら、 [0 for _ in range(n+1)] でもよさそう。
    for from_v, to_v in es:
        outs[from_v].append(to_v)
        # ins[to_v] += 1

    @lru_cache()
    def max_len(v):
        if not outs[v]:
            return 0
        else:
            return max([max_len(x)+1 for x in outs[v]])

    print(max([max_len(x) for x in range(1,N+1)]))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import unittest

class Solution(object):
	def __init__(self):
		self.graph = {}
		self.m = 0
		self.n = 0

	def readInput(self):
		a = sys.stdin.readline().split()
		self.n = int(a[0])
		self.m = int(a[1])
		for i in xrange(self.m):
			a = sys.stdin.readline().split()
			if int(a[0]) not in self.graph.keys():
				self.graph[int(a[0])] = []
			self.graph[int(a[0])].append(int(a[1]))
		#Read the height line		
		#print self.graph

	def findLongestPath(self):
		#Do DFS for each node
		max_path = 0
		memo = {}
		for v in xrange(1, self.n+1):
			dfs = []
			local_max = 0
			dfs.append((v,local_max))
			while len(dfs) != 0:
				node, l = dfs.pop()
				if node in memo.keys():
					local_max = max(local_max, l + memo[node])
				else:
					local_max = max(local_max, l)
					if node in self.graph.keys():
						for nbr in self.graph[node]:
							dfs.append((nbr, l + 1))
			memo[v] = local_max
			max_path = max(max_path, local_max)
		return max_path

if __name__ == '__main__':
	s = Solution()
	s.readInput()
	print s.findLongestPath()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Solution(object):
	def __init__(self):
		self.graph = {}
		self.m = 0
		self.n = 0

	def readInput(self):
		a = sys.stdin.readline().split()
		self.n = int(a[0])
		self.m = int(a[1])
		for i in xrange(self.m):
			a = sys.stdin.readline().split()
			if int(a[0]) not in self.graph.keys():
				self.graph[int(a[0])] = []
			self.graph[int(a[0])].append(int(a[1]))
		#Read the height line		
		#print self.graph

	def findLongestPath(self):
		#Do DFS for each node
		max_path = 0
		for v in xrange(1, self.n+1):
			dfs = []
			dfs.append((v,0))
			while len(dfs) != 0:
				node, l = dfs.pop()
				max_path = max(max_path, l)
				if node in self.graph.keys():
					for nbr in self.graph[node]:
						dfs.append((nbr, l + 1))
					#print dfs
		return max_path

if __name__ == '__main__':
	s = Solution()
	s.readInput()
	print s.findLongestPath()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

n, m = [int(i) for i in input().split()]

children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in input().split()]
    children[u-1].append(v-1)
    parents[v-1].append(u-1)

def longest_path(children, parents, n):
    f = [None] * n
    targets = [x for y in children.values() for x in y]
    starts = [v for v in range(n) if v not in targets]

    # print f
    for i in range(n):
        get_f(children, parents, f, i)

    # print f
    return max(f)

def get_f(children, parents, f, i):
    if f[i] != None:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], get_f(children, parents, f, v) + 1)

    return f[i]

# def longest_path(children, parents, n):
#     targets = [x for y in children.values() for x in y]
#     starts = [v for v in range(n) if v not in targets]
#     f = [None] * n
    
#     Q = deque([])
#     for v in starts:
#         f[v] = 0
#         Q.append((v, 0))

#     output = 0
#     while len(Q) > 0:
#         node, length = Q.pop()
#         output = max(output, length)
#         for v in children[node]:
#             Q.append((v, length+1))

#     return output

print(longest_path(children, parents, n))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

n, m = [int(i) for i in input().split()]

children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in input().split()]
    children[u-1].append(v-1)
    parents[v-1].append(u-1)

def longest_path(children, parents, n):
    f = [None] * n
    targets = [x for y in children.values() for x in y]
    starts = [v for v in range(n) if v not in targets]

    for v in starts:
        f[v] = 0

    # print f
    for i in range(n):
        get_f(children, parents, f, i)

    # print f
    return max(f)

def get_f(children, parents, f, i):
    if f[i] != None:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], get_f(children, parents, f, v) + 1)

    return f[i]

# def longest_path(children, parents, n):
#     targets = [x for y in children.values() for x in y]
#     starts = [v for v in range(n) if v not in targets]
#     f = [None] * n
    
#     Q = deque([])
#     for v in starts:
#         f[v] = 0
#         Q.append((v, 0))

#     output = 0
#     while len(Q) > 0:
#         node, length = Q.pop()
#         output = max(output, length)
#         for v in children[node]:
#             Q.append((v, length+1))

#     return output

print(longest_path(children, parents, n))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

n, m = [int(i) for i in raw_input().split()]

children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in raw_input().split()]
    children[u-1].append(v-1)
    parents[v-1].append(u-1)

def longest_path(children, parents, n):
    f = [None] * n
    targets = [x for y in children.values() for x in y]
    starts = [v for v in range(n) if v not in targets]

    for v in starts:
        f[v] = 0

    # print f
    for i in range(n):
        get_f(children, parents, f, i)

    # print f
    return max(f)

def get_f(children, parents, f, i):
    if f[i] != None:
        return f[i]

    for v in parents[i]:
        f[i] = max(f[i], get_f(children, parents, f, v) + 1)

    return f[i]

# def longest_path(children, parents, n):
#     targets = [x for y in children.values() for x in y]
#     starts = [v for v in range(n) if v not in targets]
#     f = [None] * n
    
#     Q = deque([])
#     for v in starts:
#         f[v] = 0
#         Q.append((v, 0))

#     output = 0
#     while len(Q) > 0:
#         node, length = Q.pop()
#         output = max(output, length)
#         for v in children[node]:
#             Q.append((v, length+1))

#     return output

print(longest_path(children, parents, n))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

n, m = [int(i) for i in raw_input().split()]

children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in raw_input().split()]
    children[u-1].append(v-1)
    parents[v-1].append(u-1)

# def longest_path(children, parents, n):
#     f = [None] * n
#     targets = [x for y in children.values() for x in y]
#     starts = [v for v in range(n) if v not in targets]

#     for v in starts:
#         f[v] = 0

#     # print f
#     for i in range(n):
#         get_f(children, parents, f, i)

#     # print f
#     return max(f)

def get_f(children, parents, f, i):
    if f[i] != None:
        return f[i]

    for v in parents[i]:
        f[i] = max(f[i], get_f(children, parents, f, v) + 1)

    return f[i]

def longest_path(children, parents, n):
    targets = [x for y in children.values() for x in y]
    starts = [v for v in range(n) if v not in targets]
    f = [None] * n
    

    Q = deque([])
    for v in starts:
        f[v] = 0
        Q.append((v, 0))

    output = 0
    while len(Q) > 0:
        node, length = Q.pop()
        output = max(output, length)
        for v in children[node]:
            Q.append((v, length+1))

    return output

print(longest_path(children, parents, n))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

n, m = [int(i) for i in raw_input().split()]

children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in raw_input().split()]
    children[u-1].append(v-1)
    parents[v-1].append(u-1)

# def longest_path(children, parents, n):
#     f = [None] * n
#     targets = [x for y in children.values() for x in y]
#     starts = [v for v in range(n) if v not in targets]

#     for v in starts:
#         f[v] = 0

#     # print f
#     for i in range(n):
#         get_f(children, parents, f, i)

#     # print f
#     return max(f)

def get_f(children, parents, f, i):
    if f[i] != None:
        return f[i]

    for v in parents[i]:
        f[i] = max(f[i], get_f(children, parents, f, v) + 1)

    return f[i]

def longest_path(children, parents, n):
    targets = [x for y in children.values() for x in y]
    starts = [v for v in range(n) if v not in targets]
    f = [None] * n
    

    Q = deque([])
    for v in starts:
        f[v] = 0
        Q.append((v, 0))

    output = 0
    while len(Q) > 0:
        node, length = Q.popleft()
        output = max(output, length)
        for v in children[node]:
            Q.append((v, length+1))

    return output

print(longest_path(children, parents, n))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, m = [int(i) for i in raw_input().split()]

children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in raw_input().split()]
    children[u-1].append(v-1)
    parents[v-1].append(u-1)

def longest_path(children, parents, n):
    f = [None] * n
    targets = [x for y in children.values() for x in y]
    starts = [v for v in range(n) if v not in targets]

    for v in starts:
        f[v] = 0

    # print f
    for i in range(n):
        get_f(children, parents, f, i)

    # print f
    return max(f)

def get_f(children, parents, f, i):
    if f[i] != None:
        return f[i]

    for v in parents[i]:
        f[i] = max(f[i], get_f(children, parents, f, v) + 1)

    return f[i]

print(longest_path(children, parents, n))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, list_of_xy = read()
    result = think(n, list_of_xy)
    write(result)


def read():
    n, m = read_int(2)
    list_of_xy = []
    for i in range(m):
        list_of_xy.append(read_int(2))
    return n, list_of_xy


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, list_of_xy):
    num_of_input_edges = [0 for _ in range(n + 1)]
    num_of_output_edges = [0 for _ in range(n + 1)]

    invalid_value = -1
    length_of_longest_path_start_from = [invalid_value for _ in range(n + 1)]

    for x, y in list_of_xy:
        num_of_input_edges[y] += 1
        num_of_output_edges[x] += 1

    for i in range(1, len(num_of_input_edges)):
        if num_of_output_edges[i] == 0:
            length_of_longest_path_start_from[i] = 0

    for i in range(1, len(num_of_input_edges)):
        if num_of_input_edges[i] == 0:
            update_logest_path_start_from(i, list_of_xy, length_of_longest_path_start_from, invalid_value)

    return max(length_of_longest_path_start_from)


def update_logest_path_start_from(start_from, list_of_xy, length_of_longest_path_start_from, invalid_value):
    if length_of_longest_path_start_from[start_from] != invalid_value:
        return

    subset_of_list_of_xy = list(filter(lambda x: x[0] == start_from, list_of_xy))
    for x, y in subset_of_list_of_xy:
        if length_of_longest_path_start_from[y] == invalid_value:
            update_logest_path_start_from(y, list_of_xy, length_of_longest_path_start_from, invalid_value)
            length_of_longest_path_start_from[x] = max(length_of_longest_path_start_from[x], length_of_longest_path_start_from[y] + 1)
        else:
            length_of_longest_path_start_from[x] = max(length_of_longest_path_start_from[x], length_of_longest_path_start_from[y] + 1)


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys

input = sys.stdin.readline

N, M = map(int, input().split())

es = [[int(x) for x in input().split()] for _ in range(M)]

outs = defaultdict(list)
ins = defaultdict(list)
cnt = defaultdict(int)

for v1, v2 in es:
    outs[v1].append(v2)
    cnt[v2] += 1
    ins[v2].append(v1)

q = deque(v1 for v1 in range(1, N+1) if cnt[v1] == 0)
ts = []

while q:
    v1 = q.popleft()
    ts.append(v1)
    for v2 in outs[v1]:
        cnt[v2] -= 1
        if cnt[v2] == 0:
            q.append(v2)

dp = [0 for _ in range(N)]
dp[0] = 0

for i in range(N-1):
    if len(ins[ts[i+1]]) > 0:
        for j in ins[ts[i+1]]:
            dp[i+1] = max(dp[i+1], dp[ts.index(j)] + 1)

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())

es = [[int(x) for x in input().split()] for _ in range(M)]

outs = defaultdict(list)
ins = defaultdict(list)
cnt = defaultdict(int)

for v1, v2 in es:
    outs[v1].append(v2)
    cnt[v2] += 1
    ins[v2].append(v1)

q = deque(v1 for v1 in range(1, N+1) if cnt[v1] == 0)
ts = []

while q:
    v1 = q.popleft()
    ts.append(v1)
    for v2 in outs[v1]:
        cnt[v2] -= 1
        if cnt[v2] == 0:
            q.append(v2)

dp = [0 for _ in range(N)]
dp[0] = 0

for i in range(N-1):
    if len(ins[ts[i+1]]) > 0:
        for j in ins[ts[i+1]]:
            dp[i+1] = max(dp[i+1], dp[ts.index(j)] + 1)
            
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:

""""
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
"""

N, M = map(int, raw_input().split())

G = []
for _ in xrange(M):
    G.append(map(int, raw_input().split()))

h = [0]*(N+1)

for eg in G:
    h[eg[1]]+=1

que = []

for i in xrange(1, N+1):
    if h[i] == 0: que.append(i)

dp = [0]*(N+1)

while len(que)>0:
    now = que.pop(0)
    for eg in G:
        if eg[0]==now:
            h[eg[1]]-=1
            if h[eg[1]]==0:
                que.append(eg[1])
                dp[eg[1]] = max(dp[eg[0]] + 1, dp[eg[1]])

print max(dp)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(20000)
def getMax(d,n,c):
    global bs
    if len(d[n])==0:
        bs=max(bs,c)

    for k in d[n]:
        getMax(d,k,c+1)

n,m=map(int,input().split())
d={}
for j in range(1,n+1):
    d[j]=[]
for i in range(m):
    a,b=map(int,input().split())
    d[a].append(b)
bs=-1
for i in range(1,n+1):
    c=0
    getMax(d,i,c)
print(bs)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def topological_sort(G):
    V = len(G)      # グラフの頂点数を取得
    indeg = [0]*V   # 各頂点の入次数を記録。indeg[i]は頂点iの入次数を表す。
    for u in G:
        for v in u:
            indeg[v] += 1
    res = [False]*V        # ソート結果を記録
    ct = 0
    dq = deque([i for i in range(V) if indeg[i] == 0])  # 入次数0の頂点を格納
    while dq:  # 入次数0の頂点を除いたグラフの中で入次数0の点を探し、入次数0の点がなくなるまで繰り返す
        u = dq.popleft()
        res[ct] = u
        ct += 1
        for v in G[u]:
            indeg[v] -= 1       # uから辺が伸びていた先の頂点の入次数を1減らす
            if indeg[v] == 0:   # 入次数が0の点があればキューに入れる
                dq.append(v)
    return res


N, M = map(int, input().split())

G = [[] for _ in range(N)]
inn = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    inn[y-1].append(x-1)

G_t = topological_sort(G)

dp = [0]*N  # トポロジカルソート後のi番目の頂点までの最長距離

for i in range(1, N):
    for j in inn[G_t[i]]:
        dp[i] = max(dp[i], dp[G_t.index(j)] + 1)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import heapq


def topological_sort(G):
    """
    グラフをトポロジカルソートする。与えられたグラフがトポロジカルソートできない(DAGでない)場合は-1を返す。
    プライオリティキューを用いて、頂点番号の小さいものを優先的にソートする。
    heapqモジュールをインポートする必要がある。

    Parameters
    ----------
    G : ソートしたいグラフ。0-indexedの隣接リスト型。

    Returns
    -------
    右向きにソートしたグラフの頂点のリスト。グラフがDAGでない場合は-1を返す。
    """
    V = len(G)      # グラフの頂点数を取得
    indeg = [0]*V   # 各頂点の入次数を記録。indeg[i]は頂点iの入次数を表す。
    for u in G:
        for v in u:
            indeg[v] += 1
    res = []        # ソート結果を記録
    hq = [i for i in range(V) if indeg[i] == 0]  # 入次数0の頂点を格納
    while hq:  # 入次数0の頂点を除いたグラフの中で入次数0の点を探し、入次数0の点がなくなるまで繰り返す
        u = heapq.heappop(hq)   # 頂点番号の小さいものを優先
        res.append(u)
        for v in G[u]:
            indeg[v] -= 1       # uから辺が伸びていた先の頂点の入次数を1減らす
            if indeg[v] == 0:   # 入次数が0の点があればキューに入れる
                heapq.heappush(hq, v)
    if len(res) == V:
        return res
    else:
        return -1


N, M = map(int, input().split())

G = [[] for _ in range(N)]
inn = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    inn[y-1].append(x-1)

G_t = topological_sort(G)

dp = [0]*N  # トポロジカルソート後のi番目の頂点までの最長距離

for i in range(1, N):
    for j in inn[G_t[i]]:
        dp[i] = max(dp[i], dp[G_t.index(j)] + 1)

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
# Enter your code here. Read input from STDIN. Print output to STDOUT
from collections import deque
import sys
input=sys.stdin.readline
range=xrange
N,M=list(map(int,input().strip().split(' ')))
checked=[1]*(N+1)
checked[0]=1
graph2=[[] for i in range(N+1)]

for _ in range(M):
    a,b=list(map(int,input().strip().split(' ')))
    checked[a]=0
    graph2[b]+=[a]

dp=[0]*(N+1)
q=deque([])
for i in range(1,N+1):
    if checked[i]==1:
        q+=[i]
MAX=0
while q:
    node=q.popleft()
    for adj in graph2[node]:
        dp[adj]=max(dp[adj],dp[node]+1)
        MAX=max(MAX,dp[adj])
        if checked[adj]==0:
            q+=[adj]
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
# Enter your code here. Read input from STDIN. Print output to STDOUT
from collections import deque
import sys
input=sys.stdin.readline
N,M=list(map(int,input().strip().split(' ')))
checked=[1]*(N+1)
checked[0]=1
graph2=[[] for i in range(N+1)]

for _ in range(M):
    a,b=list(map(int,input().strip().split(' ')))
    checked[a]=0
    graph2[b]+=[a]

dp=[0]*(N+1)
q=deque([])
for i in range(1,N+1):
    if checked[i]==1:
        q+=[i]
MAX=0
while q:
    node=q.popleft()
    for adj in graph2[node]:
        dp[adj]=max(dp[adj],dp[node]+1)
        MAX=max(MAX,dp[adj])
        if checked[adj]==0:
            q+=[adj]
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
N,M=list(map(int,sys.stdin.readline().strip().split(' ')))
checked=[1]*N
graph2=[[] for i in xrange(N)]
for _ in xrange(M):
    a,b=list(map(int,sys.stdin.readline().strip().split(' ')))
    a-=1
    b-=1
    checked[a]=0
    graph2[b]+=[a]

dp=[0]*N
q=deque([])
for i in xrange(N):
    if checked[i]==1:
        q+=[i]
MAX=0    
while q:
    node=q.popleft()
    for i in xrange(len(graph2[node])):
        adj=graph2[node][i]
        dp[adj]=max(dp[adj],dp[node]+1)
        MAX=max(MAX,dp[adj])
        if checked[adj]==0:
            q+=[adj]
sys.stdout.write(str(MAX))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
N,M=list(map(int,sys.stdin.readline().strip().split(' ')))
checked=[1]*N
graph2=[[] for i in range(N)]
for _ in range(M):
    a,b=list(map(int,sys.stdin.readline().strip().split(' ')))
    a-=1
    b-=1
    checked[a]=0
    graph2[b]+=[a]

dp=[0]*N
q=deque([])
for i in range(N):
    if checked[i]==1:
        q+=[i]
MAX=0    
while q:
    node=q.popleft()
    for adj in graph2[node]:
        dp[adj]=max(dp[adj],dp[node]+1)
        MAX=max(MAX,dp[adj])
        if checked[adj]==0:
            q+=[adj]
sys.stdout.write(str(MAX))

Submission status: Time Limit Exceeded

Solution code:
N,M=list(map(int,input().strip().split(' ')))
graph1=[[] for i in range(N)]
graph2=[[] for i in range(N)]
for _ in range(M):
    a,b=list(map(int,input().strip().split(' ')))
    a-=1
    b-=1
    graph1[a]+=[b]
    graph2[b]+=[a]

from collections import deque
dp=[0]*N
checked=[0]*N
q=deque([])
for i in range(N):
    if graph1[i]==[]:
        q+=[i]
        checked[i]=1
while q:
    node=q.popleft()
    for adj in graph2[node]:
        dp[adj]=max(dp[adj],dp[node]+1)
        if checked[adj]==0:
            q+=[adj]
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

from heapq import *
f_inf = float('inf')

def dijkstra(start,node,edge):
    #始点sから各頂点への距離
    #node:頂点数
    #d:各頂点へのコスト(存在しないときはinf)
    d = [0] * node
    d[start] = 0
    #q:キュー(スタートからのコスト,頂点)
    #スタートをキューに入れる
    q = [(0,start)]
    while(len(q) != 0):
    #キューの先頭を取得
      ci, i = heappop(q)
    #キューの先頭から繋がっている頂点を探索
      for j in edge[i]:
        nc = ci + 1
        d[j] = nc
        heappush(q, (nc, j))
    return max(d)
#入力
N,M = (int(x) for x in input().split())
#エッジ
E = [[] for _ in [0]*N]

for i in range(M):
  a,b = (int(x) for x in input().split())
  E[a-1].append(b-1)

ans = 0
for i in range(N):
  ans = max(ans, dijkstra(i,N,E))


#出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
f_inf = float('inf')

def dijkstra(start,node,edge):
    #始点sから各頂点への距離
    #node:頂点数
    #d:各頂点へのコスト(存在しないときはinf)
    d = [0] * node
    d[start] = 0
    #q:キュー(スタートからのコスト,頂点)
    #スタートをキューに入れる
    q = [(0,start)]
    while(len(q) != 0):
    #キューの先頭を取得
      ci, i = heappop(q)
    #キューの先頭から繋がっている頂点を探索
      for j in edge[i]:
        nc = ci + 1
        d[j] = nc
        heappush(q, (nc, j))
    return max(d)
#入力
N,M = (int(x) for x in input().split())
#エッジ
E = [[] for _ in [0]*N]

for i in range(M):
  a,b = (int(x) for x in input().split())
  E[a-1].append(b-1)

ans = 0
for i in range(N):
  ans = max(ans, dijkstra(i,N,E))


#出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())

graph = [[] for _ in range(n + 1)]

for i in range(m):
    f, t = map(int, input().split())
    graph[t].append(f)

dp = [-1] * (n + 1)
def dfs(now):
    if dp[now] != -1:
        return dp[now]

    if not graph[now]:
        return 0

    r = max(dfs(parent) for parent in graph[now]) + 1
    dp[now] = r
    return r

print(max(dfs(i) for i in range(1, n + 1)))