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: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
dp = [-1]*N


def dfs(n):
    global dp
    if dp[n] > 0:
        return dp[n]

    ma = 0
    for b in G[n]:
        ma = max(ma, dfs(b) + 1)
    dp[n] = ma
    return ma


def main():
    global dp
    for i in range(N):
        dp[i] = dfs(i)
    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
n, m = [int(x) for x in input().strip().split()]
graph = {}
for i in range(m):
    u, v = [int(x) for x in input().strip().split()]
    if u not in graph:
        graph[u] = []
    graph[u].append(v)

def dfs(n):
    visited[n] = 1
    if n in graph:
        for node in graph[n]:
            if node not in visited:
                dfs(node)
            dp[n-1] = max(dp[n-1],dp[node-1]+1)


visited = {}
dp = [0 for i in range(n)]

for i in range(1,n+1):
    if i not in visited:
        dfs(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
xy = [list(map(int, input().split())) for _ in range(M)]
to = [[]*(N+1) for _ in range(N+1)]
for i in range(M):
    x,y=xy[i]
    to[x].append(y)

dp = [0]*(N+1)

def saiki(v):
    for u in to[v]:
        if dp[u] < dp[v]+1:
            dp[u]=dp[v]+1
            saiki(u)

count = [True]*(N+1)
count[0] = False
for i in range(M):
    count[xy[i][1]] = False

for i in range(1,N+1):
    if count[i]:
        saiki(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
N,M = [int(x) for x in input().split()]
E ={i: [] for i in range(1, N+1)}
for _ in range(M):
  u,v = [int(x) for x in input().split()]
  E[u].append(v)
#print(E)
dp =[-1]*(N+1)
def memo(v):
  if dp[v]!= -1:
    return dp[v]
  res = 0
  for nv in E[v]:
    res = max(res,memo(nv)+1)
  dp[v] =res
  return dp[v]
res = 0
for v in range(1,N+1):
  res = max(res,memo(v))
print(res)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

maxDist = [0 for i in range(N+1)]
in_degree = [0 for i in range(N+1)]
adj_list = [[] for i in range(N+1)]

for i in range(M):
    x, y = map(int, input().split())
    adj_list[x].append(y)
    in_degree[y] += 1

for node in range(1, N+1):
    adj_list[0].append(node)
    in_degree[node] += 1

# dp[i] = maximum length of path ending at i
flattenedNodes = []
def dfs(node):
    for child in adj_list[node]:
        maxDist[child] = max(maxDist[child], 1 + maxDist[node])
        in_degree[child] -= 1
        if in_degree[child] == 0:
            dfs(child)
            
dfs(0)
print(max(maxDist) - 1)

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
def dfs(v):
    if d[v] != -1:
        return d[v]
    res = -1
    for u in e[v]:
        res = max(res, dfs(u))
    res += 1
    d[v] = res
    return res


n, m = map(int, input().split())
e = tuple(set() for _ in range(n))
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    e[x].add(y)

d = [-1] * n
res = -1
for v in range(n):
    res = max(res, dfs(v))
print(res)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())

maxDist = [0 for i in range(N)]
in_degree = [1 for i in range(N)]
adj_list_f = [[] for i in range(N)]
adj_list_b = [[] for i in range(N)]

for i in range(M):
    x, y = map(lambda x:int(x)-1, input().split())
    adj_list_f[x].append(y)
    adj_list_b[y].append(x)
    in_degree[y] += 1

# dp[i] = maximum length of path ending at i
def dfs(node):
    children = adj_list_f[node] if node != -1 else [i for i in range(N)]
    for child in children:
        if node == -1:
            maxDist[child] = max(maxDist[child], 1)
        else:
            maxDist[child] = max(maxDist[child], 1 + maxDist[node])
        in_degree[child] -= 1
        if in_degree[child] == 0:
            dfs(child)
            
dfs(-1)
print(max(maxDist) - 1)

Submission status: Runtime Error

Solution code:
def dfs(node, edges, dp, visited):
    visited.add(node)
    for child in edges.get(node, []):
        if not child in visited:
            dfs(child, edges, dp, visited)
        dp[node] = max(dp[node], 1 + dp[child])

def main(n, edges):
    dp = [0] * (n + 1)
    visited = set()
    for i in range(1, n + 1):
        if not i in visited:
            dfs(i, edges, dp, visited)
    return max(dp)

assert main(6, { 2: [3], 4: [5], 5: [6] }) == 2
assert main(4, { 1: [2, 3], 3: [2, 4], 2: [4] }) == 3

n, m = map(int, input().split())
edges = {}
for _ in range(m):
    u, v = map(int, input().split())
    if u not in edges:
        edges[u] = set([v])
    else:
        edges[u].add(v)
ans = main(n, edges)
print(ans)

Submission status: Runtime Error

Solution code:
import collections
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    for _ in range(M):
        x, y = map(int, input().split())
        graph[x].append(y)

    memo = dict()
    def helper(node):
        if node in memo:
            return memo[node]

        max_l = 0
        for nxt in graph[node]:
            max_l = max(max_l, helper(nxt) + 1)
        memo[node] = max_l
        return max_l

    max_l = 0
    for i in range(1, N+1):
        l = helper(i)
        max_l = max(max_l, l)
    return max_l

if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if i < 0 or i >= len(f):
        return 0

    if f[i] != -1:
        return f[i]

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

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):

    if f[i] != -1:
        return f[i]

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

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):

    if f[i] != -1:
        return f[i]

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

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if not f:
    print 0
else:
    print max(f)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if f[i] != -1:
        return f[i]

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

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

print max(f)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if f[i] != -1:
        return f[i]

    f[i] = float("-inf")
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

print max(f)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if f[i] != -1:
        return f[i]

    f[i] = float("-inf")
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

print max(f)
s

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

parents = {}

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    if v-1 in parents:
        parents[v-1].append(u-1)
    else:
        parents[v-1] = [u-1]
    i += 1

def calc_f(parents, f, i):
    if f[i] != -1:
        return f[i]

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

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

print max(f)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

parents = {}

for _ in xrange(m):
    u, v = [int(x) for x in raw_input().split()]
    if v-1 in parents:
        parents[v-1].append(u-1)
    else:
        parents[v-1] = [u-1]

def calc_c(parents, f, i):
    if f[i] != -1:
        return f[i]

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

    return f[i]

f = [-1] * n
for i in xrange(n):
    calc_c(parents, f, i)

print max(f)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

parents = defaultdict(list)

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

def calc_c(parents, f, i):
    if f[i] != -1:
        return f[i]

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

    return f[i]

f = [-1] * n
for i in range(n):
    calc_c(parents, f, i)

print max(f)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque

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

parents = defaultdict(list)

for _ in xrange(m):
    inp = raw_input().split()
    u = int(inp[0])
    v = int(inp[1])
    parents[v-1].append(u-1)

def get_f(parents, f, i):
    if f[i] != -1:
        return f[i]

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

    return f[i]

def longest_path(parents, n):
    f = [-1 for _ in xrange(n)]

    for i in xrange(n):
        get_f(parents, f, i)

    return max(f)

print longest_path(parents, n)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque

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

parents = defaultdict(list)

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

def get_f(parents, f, i):
    if f[i] != -1:
        return f[i]

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

    return f[i]

def longest_path(parents, n):
    f = [-1 for _ in xrange(n)]

    for i in xrange(n):
        get_f(parents, f, i)

    return max(f)

print longest_path(parents, n)

Submission status: Runtime Error

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 get_f(parents, f, i):
    if i in f:
        return f[i]

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

    return f[i]

def longest_path(parents, n):
    f = defaultdict(lambda: -1)
    # 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 xrange(n):
        get_f(parents, f, i)

    # print f
    return max(f)

# 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(parents, n))

Submission status: Runtime Error

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 get_f(parents, f, i):
    if i >= len(f):
        return 0
        
    if f[i] != -1:
        return f[i]

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

    return f[i]

def longest_path(parents, n):
    f = [-1 for _ in xrange(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(parents, f, i)

    # print f
    return max(f)

# 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(parents, n))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque

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

# children = defaultdict(list)
parents = {}

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

def get_f(parents, f, i):
    if f[i] != -1:
        return f[i]

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

    return f[i]

def longest_path(parents, n):
    f = [-1 for _ in xrange(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(parents, f, i)

    # print f
    return max(f)

# 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(parents, n))

Submission status: Runtime Error

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(parents, n):
    f = [-1 for _ in xrange(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(parents, f, i)

    # print f
    return max(f)

def get_f(parents, f, i):
    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], get_f(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(parents, n))

Submission status: Runtime Error

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(parents, n):
    f = [-1] * 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(parents, f, i)

    # print f
    return max(f)

def get_f(parents, f, i):
    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], get_f(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(parents, n))

Submission status: Runtime Error

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(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(parents, f, i)

    # print f
    return max(f)

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

    for v in parents[i]:
        f[i] = max(f[i], get_f(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(parents, n))

Submission status: Runtime Error

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(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(parents, f, i)

    # print f
    return max(f)

def get_f(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(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(parents, n))

Submission status: Runtime Error

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]

    # 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: Runtime Error

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: Runtime Error

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]

    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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
N,M = map(int,input().split())
graph = [[] for i in range(10**5 + 10)]
dp = [-1 for i in range(10**5 + 10)]

for i in range(M):
    x,y = map(int,input().split())
    graph[x-1].append(y-1)
    
def rec(v):
    if dp[v] != -1:
        return dp[v]
    tmp = 0
    for x in graph[v]:
        r = rec(x)+1
        if tmp < r:
            tmp = r
    dp[v] = tmp
    return dp[v]

result = 0
for i in range(N):
    r = rec(i)
    result = r if r>result else result
print(result)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
graph = [[] for i in range(10**5 + 10)]
dp = [-1 for i in range(10**5 + 10)]

for i in range(M):
    x,y = map(int,input().split())
    graph[x-1].append(y-1)
    
def rec(v):
    if dp[v] != -1:
        return dp[v]
    tmp = 0
    for x in graph[v]:
        r = rec(x)+1
        if tmp < r:
            tmp = r
    dp[v] = tmp
    return dp[v]

result = 0
for i in range(N):
    r = rec(i)
    result = r if r>result else result
print(result)

Submission status: Runtime Error

Solution code:
def max_depth(i):
    global adj, dp
    if len(adj[i])==0:
        return 0
    elif i in dp.keys():
        return dp[i]
    else:
        ans = -1
        for j in adj[i]:
            ans = max(max_depth(j), ans)
        dp[i] = ans+1
        return ans+1

n,m = [int(j) for j in input().split()]
adj = [[] for i in range(n)]
s = set()
s1 = set(range(n))
for i in range(m):
    x,y = [int(j)-1 for j in input().split()]
    adj[x].append(y)
    s.add(y)
s2 = s1-s
dp = dict()
for i in s2:
    max_depth(i)
print(max(dp.values()))

Submission status: Runtime Error

Solution code:
def max_depth(i):
    global adj, dp
    if len(adj[i])==0:
        return 0
    elif i in dp.keys():
        return dp[i]
    else:
        ans = -1
        for j in adj[i]:
            ans = max(max_depth(j), ans)
        dp[i] = ans+1
        return ans+1

n,m = [int(j) for j in input().split()]
adj = [[] for i in range(n)]
s = set()
s1 = set(range(n))
for i in range(m):
    x,y = [int(j)-1 for j in raw_input().split()]
    adj[x].append(y)
    s.add(y)
s2 = s1-s
dp = dict()
for i in s2:
    max_depth(i)
print(max(dp.values()))

Submission status: Runtime Error

Solution code:
def max_depth(i):
    global adj, dp
    if len(adj[i])==0:
        return 0
    elif i in dp.keys():
        return dp[i]
    else:
        ans = -1
        for j in adj[i]:
            ans = max(max_depth(j), ans)
        dp[i] = ans+1
        return ans+1

n,m = [int(j) for j in raw_input().split()]
adj = [[] for i in range(n)]
s = set()
s1 = set(range(n))
for i in range(m):
    x,y = [int(j)-1 for j in raw_input().split()]
    adj[x].append(y)
    s.add(y)
s2 = s1-s
dp = dict()
for i in s2:
    max_depth(i)
print(max(dp.values()))

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))

g = [set() for x in range(n)]

dp = [-1]*n

for i in range(m):
    u, v = list(map(int, input().split()))
    u-=1
    v-=1
    g[u].add(v)

def solve(u):

    if (dp[u]!=-1):
        return dp[u]
    ans = 0
    for v in g[u]:
        ans = max(ans, 1+solve(v))
    dp[u]=ans
    return ans

ans =0
for i in range(n):
    ans = max(ans, solve(i))

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())

root = [[] for _ in range(n)]

for i in range(m):
    x, y = map(int, input().split())
    root[x-1].append(y-1)

memo = ["empty" for _ in range(n)]

def dp(x):
    if memo[x] == "empty":
        res = 0
        for i in root[x]:
            res = max(res, dp(i)+1)
        memo[x] = res

    return memo[x]

for j in range(n):
    dp(j)

print(max(memo))

Submission status: Runtime Error

Solution code:
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 100


adj=[]
n,m = map(int,raw_input().split())
for i in range(n+1):
	adj.append([])
dp=[0]*(n+1)	
def dd(l):
	if(dp[l]!=-1):
		return dp[l]
	ma=dd(adj[l][0])
	for j in range(1,len(adj[l])):
		ma=max(ma,dd(adj[l][j]))
	dp[l]=ma+1
	return ma+1	
for i in range(m):
	x,y = map(int,raw_input().split())
	adj[y].append(x)
	dp[y]=-1
ans=[]
for i in range(1,n+1):
	ans.append(dd(i))
	# print i
print max(ans)

Submission status: Runtime Error

Solution code:
def dfs(dp,edges,node,visited):
    if node not in visited:
        visited.add(node)
        for kid in edges[node]:
            dfs(dp,edges,kid,visited)
            #print(dp,node,kid)
            dp[node-1] = max(dp[node-1],dp[kid-1])
        if edges[node]:
            dp[node-1] += 1

def solve(edges,n):
    dp = [0]*n
    visited = set()
    for i in range(1,n+1):
        if i not in visited:
            #print(i)
            dfs(dp,edges,i,visited)

    #print(dp)
    print(max(dp))

def main():
    n,m = map(int,raw_input().split())
    edges = {}
    for i in range(1,n+1):
        edges[i] = []

    for i in range(m):
        x,y = map(int,raw_input().split())
        edges[x].append(y)

    solve(edges,n)


main()