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:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def get_longest(x, longest, edges):
    if longest[x] is not None:
        return longest[x]
    if not edges[x]:
        return 0
    result = max([get_longest(y, longest, edges)
                  for y in edges[x]])
    return result + 1


def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    edges = defaultdict(set)
    for i in range(M):
        x, y = map(int, input().split())
        edges[x].add(y)

    longest = [None] * (N + 1)
    for x in range(N):
        x += 1
        if longest[x] is None:
            longest[x] = get_longest(x, longest, edges)

    print(max(longest[1:]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
"""
Simple Version
Python TLE https://atcoder.jp/contests/dp/submissions/14906600
PyPy TLE https://atcoder.jp/contests/dp/submissions/14906630
"""
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = [-1] * (N + 1)
    for i in range(N + 1):
        if not edges[i]:
            longest[i] = 0

    def get_longest(start):
        ret = longest[start]
        if ret != -1:
            return ret

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = {}

    def get_longest(start):
        if start in longest:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = {}

    def get_longest(start):
        if start in longest:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


def solve(N, M, edges):
    longest = {}

    def get_longest(start):
        if longest.get(start) != None:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, M = na()
node_dic = {}
no_in = [1] * N

for _ in range(M):
    x, y = na()
    if x-1 in node_dic:
        node_dic[x-1].append(y-1)
    else:
        node_dic[x-1] = [y-1]
    no_in[y-1] = 0


# print(node_dic, no_in)


ans_array = [0] * N

edge = deque([])

for i, x in enumerate(no_in):
    if x == 1:
        deque.append(edge, i)

while(len(edge)):
    e = deque.popleft(edge)
    if e in node_dic:
        for x in node_dic[e]:
            deque.append(edge, x)
            ans_array[x] = max(ans_array[x], ans_array[e] + 1)
    # print(ans_array)
print(max(ans_array))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve0(N, M, edges):
    path = edges.copy()
    exists = 1
    for i in range(2, M + 1):
        next_path = defaultdict(set)
        for v1 in path:
            for v2 in path[v1]:
                if edges[v2]:
                    next_path[v1].update(edges[v2])
                    exists = i
                    # debug(": i, v1, next_path[v1]", i, v1, next_path[v1])
        if exists != i:
            # no more pathes
            break
        path = next_path
    return exists


def solve(N, M, edges):
    longest = {}

    def get_longest(start):
        if longest.get(start) != None:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


def solve(N, M, edges):
    longest = [-1] * (N + 1)

    def get_longest(start):
        if longest[start] != -1:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, dict(edges)))


def _test():
    """
    >>> as_input(T1)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve0(N, M, edges):
    path = edges.copy()
    exists = 1
    for i in range(2, M + 1):
        next_path = defaultdict(set)
        for v1 in path:
            for v2 in path[v1]:
                if edges[v2]:
                    next_path[v1].update(edges[v2])
                    exists = i
                    # debug(": i, v1, next_path[v1]", i, v1, next_path[v1])
        if exists != i:
            # no more pathes
            break
        path = next_path
    return exists


def solve(N, M, edges):
    longest = {}

    def get_longest(start):
        if longest.get(start) != None:
            return longest[start]

        next_edges = edges.get(start)
        if not next_edges:
            ret = 0
        else:
            ret = max(get_longest(v) for v in edges[start]) + 1
        longest[start] = ret
        return ret

    return max(get_longest(v) for v in edges)


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, dict(edges)))


def _test():
    """
    >>> as_input(T1)
    >>> main()
    3
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, M, edges):
    "void()"
    path = edges.copy()
    exists = 1
    for i in range(2, M + 1):
        next_path = defaultdict(set)
        for v1 in path:
            for v2 in path[v1]:
                if edges[v2]:
                    next_path[v1].update(edges[v2])
                    exists = i
                    # debug(": i, v1, next_path[v1]", i, v1, next_path[v1])
        if exists != i:
            # no more pathes
            break
        path = next_path
    return exists


T1 = """
4 5
1 2
1 3
3 2
2 4
3 4
"""


def main():
    N, M = map(int, input().split())
    edges = defaultdict(set)
    for i in range(M):
        v1, v2 = map(int, input().split())
        edges[v1].add(v2)

    print(solve(N, M, edges))


def _test():
    """
    >>> as_input(T1)
    >>> main()
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, adj = getInputs()

    # maxDistance[start]
    maxDistance = [0] * n
    overallMaxDistance = 0

    calculated = [0] * n

    for v in range(n):
        # distance[dest] (starting at v)
        distance = [0] * n
        currMaxDistance = 0

        toVisit = deque([v])

        while len(toVisit) > 0:
            curr = toVisit.popleft()

            for dest in adj[curr]:
                if calculated[dest] == 1:
                    newDistance = distance[curr] + maxDistance[dest] + 1

                    if newDistance > distance[dest]:
                        distance[dest] = newDistance

                        if distance[dest] > currMaxDistance:
                            currMaxDistance = distance[dest]
                else:
                    if distance[curr] + 1 > distance[dest]:
                        distance[dest] = distance[curr] + 1

                        if distance[dest] > currMaxDistance:
                            currMaxDistance = distance[dest]

                    toVisit.append(dest)

        maxDistance[v] = currMaxDistance
        if currMaxDistance > overallMaxDistance:
            overallMaxDistance = currMaxDistance

        calculated[v] = 1

    print(overallMaxDistance)

def getInputs():
    n, m = map(lambda x: int(x), input().split())

    adj = []
    for i in range(n):
        adj.append([])

    for i in range(m):
        a, b = map(lambda x: int(x), input().split())
        adj[a - 1].append(b - 1)

    return n, adj

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, adj = getInputs()

    # maxDistance[start]
    maxDistance = [0] * n
    overallMaxDistance = 0

    calculated = [0] * n

    for v in getVertexSequence(n, adj):
        # distance[dest] (starting at v)
        distance = [0] * n
        currMaxDistance = 0

        toVisit = deque([v])

        while len(toVisit) > 0:
            curr = toVisit.popleft()

            for dest in adj[curr]:
                if calculated[dest] == 1:
                    newDistance = distance[curr] + maxDistance[dest] + 1

                    if newDistance > distance[dest]:
                        distance[dest] = newDistance

                        if distance[dest] > currMaxDistance:
                            currMaxDistance = distance[dest]
                else:
                    if distance[curr] + 1 > distance[dest]:
                        distance[dest] = distance[curr] + 1

                        if distance[dest] > currMaxDistance:
                            currMaxDistance = distance[dest]

                    toVisit.append(dest)

        maxDistance[v] = currMaxDistance
        if currMaxDistance > overallMaxDistance:
            overallMaxDistance = currMaxDistance

        calculated[v] = 1

    print(overallMaxDistance)

def getInputs():
    n, m = map(lambda x: int(x), input().split())

    adj = []
    for i in range(n):
        adj.append([])

    for i in range(m):
        a, b = map(lambda x: int(x), input().split())
        adj[a - 1].append(b - 1)

    return n, adj

def getVertexSequence(n, adj):
    pairs = []
    for i in range(n):
        pairs.append((i, adj[i]))

    pairs.sort(key=(lambda x: len(x[1])))

    sequence = []
    for i in range(n):
        sequence.append(pairs[i][0])

    return sequence

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, adj = getInputs()

    # maxDistance[start]
    maxDistance = [0] * n
    calculated = set()

    for v in getVertexSequence(n, adj):
        # distance[dest] (starting at v)
        distance = [0] * n

        toVisit = deque([v])

        while len(toVisit) > 0:
            curr = toVisit.popleft()

            for dest in adj[curr]:
                if dest in calculated:
                    distance[dest] = max(
                        distance[dest],
                        distance[curr] + maxDistance[dest] + 1
                    )
                else:
                    if distance[curr] + 1 > distance[dest]:
                        distance[dest] = distance[curr] + 1

                    toVisit.append(dest)

        maxDistance[v] = max(distance)
        calculated.add(v)

    print(max(maxDistance))

def getInputs():
    n, m = map(lambda x: int(x), input().split())

    adj = []
    for i in range(n):
        adj.append([])

    for i in range(m):
        a, b = map(lambda x: int(x), input().split())
        adj[a - 1].append(b - 1)

    return n, adj

def getVertexSequence(n, adj):
    pairs = []
    for i in range(n):
        pairs.append((i, adj[i]))

    pairs.sort(key=(lambda x: len(x[1])))

    sequence = []
    for i in range(n):
        sequence.append(pairs[i][0])

    return sequence

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    edges[x].append(y)


def dfs(v, parent):
    visited[v] = 1
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)
        if dist[v] >= dist[v2]+1:
            continue
        dist[v] = dist[v2]+1


dist = [0]*n
visited = [0]*n

for i in range(n):
    if visited[i]:
        continue
    dfs(i, -1)

print(max(dist))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    edges[x].append(y)


def dfs(v, parent):
    visited[v] = 1
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)
        dist[v] = max(dist[v], dist[v2]+1)


dist = [0]*n
visited = [0]*n

for i in range(n):
    if visited[i]:
        continue
    dfs(i, -1)

print(max(dist))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
visit=[0]*n
B=[set() for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  visit[a-1]+=1
  B[b-1].add(a)
dp=[0]*n
from collections import deque
for i in range(n):
  if visit[i]==0:
    d=deque()
    d.append(i+1)
    while d:
      now=d.pop()
      for j in B[now-1]:
        d.append(j)
        dp[j-1]=max(dp[j-1],dp[now-1]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
visit=[0]*n
B=[list() for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  visit[a-1]+=1
  B[b-1].append(a)
dp=[0]*n
from collections import deque
for i in range(n):
  if visit[i]==0:
    d=deque()
    d.append(i+1)
    while d:
      now=d.pop()
      for j in B[now-1]:
        d.append(j)
        dp[j-1]=max(dp[j-1],dp[now-1]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
visit=[0]*n
B=[list() for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  visit[a-1]+=1
  B[b-1].append(a)
dp=[-1]*n
from collections import deque
for i in range(n):
  if visit[i]==0:
    dp[i]=0
    d=deque()
    d.append(i+1)
    while d:
      now=d.pop()
      for j in B[now-1]:
        d.append(j)
        dp[j-1]=max(dp[j-1],dp[now-1]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[list() for _ in range(n)]
B=[list() for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  A[a-1].append(b)
  B[b-1].append(a)
dp=[-1]*n
from collections import deque
for i in range(n):
  if A[i]==[]:
    dp[i]=0
    d=deque()
    d.append(i+1)
    while d:
      now=d.pop()
      for j in B[now-1]:
        d.append(j)
        dp[j-1]=max(dp[j-1],dp[now-1]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[list() for _ in range(n)]
B=[list() for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  A[a-1].append(b)
  B[b-1].append(a)
dp=[-1]*n
from collections import deque
for i in range(n):
  if A[i]==[]:
    dp[i]=0
    d=deque()
    d.append(i+1)
    while d:
      now=d.pop()
      for j in B[now-1]:
        d.append(j)
        dp[j-1]=max(dp[j-1],dp[now-1]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit, stdin


def f(i, links, dp):
    if dp[i] != -1:
        return dp[i]
    if len(links[i]) == 0:
        dp[i] = 0
    else:
        dp[i] = max(f(j, links, dp) for j in links[i]) + 1
    return dp[i]


def main():
    setrecursionlimit(10 ** 6)
    readline = stdin.readline

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

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

    dp = [-1] * N
    print(max(f(i, links, dp) for i in range(N)))


main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit, stdin


def f(i, links, dp):
    if dp[i] != -1:
        return dp[i]
    if len(links[i]) == 0:
        dp[i] = 0
    else:
        dp[i] = max(f(j, links, dp) for j in links[i]) + 1
    return dp[i]


setrecursionlimit(10 ** 6)
readline = stdin.readline

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

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

dp = [-1] * N
print(max(f(i, links, dp) for i in range(N)))

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit


def f(i, links, dp):
  if dp[i] != -1:
    return dp[i]
  if len(links[i]) == 0:
    dp[i] = 0
  else:
    dp[i] = max(f(j, links, dp) for j in links[i]) + 1
  return dp[i]


setrecursionlimit(1000000)

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

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

dp = [-1] * N
print(max(f(i, links, dp) for i in range(N)))

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit


def f(i, links, dp):
    if dp[i] != -1:
        return dp[i]
    if len(links[i]) == 0:
        dp[i] = 0
    else:
        dp[i] = max(f(j, links, dp) for j in links[i]) + 1
    return dp[i]


setrecursionlimit(10 ** 6)

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

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

dp = [-1] * N
print(max(f(i, links, dp) for i in range(N)))

Submission status: Time Limit Exceeded

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

# 隣接リストを作成
adjacencyList = [[] for _ in range(N)]

# 距離の情報
dp = [0] * N

# 入次数　（いりじすう）
deg = [0] * N

for _ in range(M):
    v, nv = map(int, input().split())
    adjacencyList[v-1].append(nv-1)
    #　入次数に1を足す
    deg[nv-1] += 1
    
queue = []

# BFS探索
# 入次数がゼロの頂点から探索を始める
for v in range(N):
    if deg[v] == 0:
        queue.append(v)

while queue:
    # 現在の頂点をqueueからpop
    v = queue.pop(0)
    for nv in adjacencyList[v]:
        # 探索済みの頂点の入次数を減らす
        deg[nv] -= 1
        
        # 完全に探索済みの頂点の入次数がゼロの時、経路の距離を出発点から計算
        if deg[nv] == 0:
            # 頂点をqueueに追加する
            queue.append(nv)
            dp[nv] = max(dp[v] + 1, dp[nv])
            
print(max(dp))

Submission status: Time Limit Exceeded

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

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

for _ in range(M):
    x,y=map(int,input().split())

    dp[x-1].append(y-1)

result=1

taisho=[]
next_taisho=[]

for i in range(N):
    if len(dp[i])>=1:
        for j in dp[i]:
            taisho.append(j)


while True:
    for k in taisho:
        if len(dp[k])>=1:
            for j in dp[k]:
                next_taisho.append(j)
    
    if len(next_taisho)==0:
        break

    else:
        result+=1
        taisho=next_taisho[0:]
        next_taisho=[]

print(result)

Submission status: Time Limit Exceeded

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

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

for _ in range(M):
    x,y=map(int,input().split())

    dp[x-1].append(y-1)

result=1

taisho=[]
next_taisho=[]

for i in range(N):
    if len(dp[i])>=1:
        taisho[len(taisho):]=dp[i]


while True:
    for k in taisho:
        if len(dp[k])>=1:
            next_taisho[len(next_taisho):]=dp[k]
    
    if len(next_taisho)==0:
        break

    else:
        result+=1
        taisho=next_taisho.copy()
        next_taisho=[]

print(result)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

dp=[-1]*100100
G=[[] for _ in range(100100)]

def dfs(v):
  if dp[v]!=-1:
    return dp[v]

  x=0
  for w in G[v]:
    r=dfs(w)+1
    x=max(x,r)

  return x

def main():
  n,k=LI()
  for _ in range(k):
    a,b=LI()
    a-=1
    b-=1
    G[a].append(b)

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

  return ans

print(main())
# main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

g=[[] for i in range(n)]
for i in range(m):
  v1,v2=map(int,input().split())
  v1-=1;v2-=1
  g[v1].append(v2)

def dfs(i):
  temp=0
  for nv in g[i]:
    temp=max(temp,dfs(nv)+1)
    
  return temp  
    
res=0
for i in range(n):
  res=max(res,dfs(i))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].append(y)

counts = [-1] * n

while -1 in counts:
    start = counts.index(-1)
    q = deque([[start, 0]])
    while q:
        i, l = q.pop()
        counts[i] = max(counts[i], l)
        for ni in G[i]:
            q.append([ni, l+1])

print(max(counts))

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10**9)

def dfs(i):
    if distance[i] != -1:
        return distance[i]
    ans = 0
    for node in graph[i]:
        ans = max(ans, dfs(node) + 1)
    return ans

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

graph = [[] for i in range(n)]
distance = [-1 for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
    
n, m = map(int, input().split())
adj = defaultdict(list)
radj = defaultdict(list)

for i in range(m):
    s, e = map(int, input().split())
    adj[s].append(e)
    radj[e].append(s)
    
mp = [0]*(n+1)
v = [0]*(n+1)
    
for i in range(1, 1+n):
    if len(adj[i]) == 0:
        q = [i]
        while q:
            e = q.pop()
            for j in radj[e]:
                mp[j] = max(mp[j], 1+mp[e])
                q.append(j)

print(max(mp))

Submission status: Time Limit Exceeded

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

  l = list([] for i in range(n))

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

    dp = [-1] * n

  def rec(v):
    if(dp[v] != -1):
      return dp[v]

    ans = 0
    test = l[v]
    for i in test:
      ans = max(ans, rec(i) + 1)
    dp[v] = ans
    return dp[v]

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

  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
    
n, m = map(int, input().split())
mp = 0

adj = defaultdict(list)

for i in range(m):
    s, e = map(int, input().split())
    adj[s].append(e)
    
for i in range(1, 1+n):
    q = [[i, 0]]

    while q:
        e, l = q.pop()

        if len(adj[e]) == 0:
            mp = max(mp, l)
        else:
            for j in adj[e]:
                q.append([j, l+1])

print(mp)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G_fix
# CreatedDate:  2020-06-05 21:28:41 +0900
# LastModified: 2020-06-05 22:03:20 +0900
#


import os
import sys
from collections import deque
#import numpy as np
#import pandas as pd


def main():
    n,m = map(int,input().split())
    path = [[] for _ in range(n+1)]
    to_cnt = [0]*(n+1)
    longest_cnt = [0]*(n+1)
    for _ in range(m):
        x,y = map(int,input().split())
        path[x].append(y)
        to_cnt[y]+=1
    
    Q = deque()
    for i in range(1,n+1):
        if to_cnt[i]==0:
            Q.append(i)

#    longest_cnt[s]=1

    while(Q):
        u = Q.popleft()
        for v in path[u]:
            to_cnt[v]-=1
            if longest_cnt[u]+1>longest_cnt[v]:
                longest_cnt[v]=longest_cnt[u]+1
            Q.append(v)
    print(max(longest_cnt))



if __name__ == "__main__":
    main()