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 python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return

#E
def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return

#F
def F():
    s = S()
    t = S()
    dp = [["" for i in range(len(t)+1)] for k in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + s[i]
            else:
                if len(dp[i][j + 1]) < len(dp[i + 1][j]):
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
    print(dp[len(s)][len(t)])
    return

#G
def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                ansb = max(ansb, ans(dp, k) + 1)
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return

#H
def H():
    return

#I
def I():
    return 
#J

#K

#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    G()

Submission status: Time Limit Exceeded

Solution code:
def topologicalsort(N,E):
    V = [0]*N
    for i in range(N):
        for y in E[i]:
            V[y] += 1
    S = [ i for i in range(N) if V[i] == 0]
    SORTED = []
    while S:
        s = S.pop(0)
        SORTED.append(s)
        for t in E[s]:
            V[t] -= 1
            if V[t] == 0:
                S.append(t)
    return SORTED
    
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
for _ in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    E[x].append(y)
V = topologicalsort(N, E)
ANS = [0]*N
for i in range(N):
    v = V[i]
    t = ANS[v]+1
    for e in E[v]:
        if t > ANS[e]:
            ANS[e] = t
print( max(ANS))

Submission status: Time Limit Exceeded

Solution code:
import heapq
def topologicalsort(N,E):
    V = [0]*N
    for i in range(N):
        for y in E[i]:
            V[y] += 1
    S = [ i for i in range(N) if V[i] == 0]
    SORTED = []
    while S:
        s = S.pop(0)
        SORTED.append(s)
        for t in E[s]:
            V[t] -= 1
            if V[t] == 0:
                S.append(t)
    return SORTED
    
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
for _ in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    E[x].append(y)
V = topologicalsort(N, E)
ANS = [0]*N
for i in range(N):
    v = V[i]
    t = ANS[v]+1
    for e in E[v]:
        if t > ANS[e]:
            ANS[e] = t
print( max(ANS))

Submission status: Time Limit Exceeded

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

N,M = map(int,input().split())
matrix = [[0]*N for i in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    matrix[x][y] = 1

dp = [-1]*N

def rec(nodes):
    if dp[nodes] != -1:
        return dp[nodes]
    res = 0
    for ne,bit in enumerate(matrix[nodes]):
        if bit == 0:continue
        option = rec(ne)+1
        if res < option:
            res = option
    dp[nodes] = res
    return dp[nodes]

ans = 0
for i in range(N):
    res = rec(i)
    if ans < res:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

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

N,M = map(int,input().split())
matrix = [[0]*N for i in range(N)]
for _ in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    matrix[x][y] = 1

dp = [-1]*N

def rec(nodes):
    if dp[nodes] != -1:
        return dp[nodes]
    dp[nodes] = 0
    for ne,bit in enumerate(matrix[nodes]):
        if bit == 0:continue
        option = rec(ne)+1
        if dp[nodes] < option:
            dp[nodes] = option
    return dp[nodes]

ans = 0
for i in range(N):
    res = rec(i)
    if ans < res:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map( int, input().split())
V = [ 1 for i in range(N)]
E = [ [] for _ in range(N)]
for _ in range(M):
    x, y = map( lambda x:x-1, map( int, input().split()))
    V[y] = 0
    E[x].append(y)
S = []
for i in range(N):
    if V[i] == 1:
        S.append(i)
Pathdistance = [-1 for _ in range(N)]
while S:
    s = S.pop(0)
    Pathdistance[s] = 0
    now = 1
    Z = []
    for t in E[s]:
        if Pathdistance[t] < now:
            Z.append(t)
            Pathdistance[t] = now
    while Z:
        T = []
        now += 1
        for z in Z:
            for t in E[z]:
                if Pathdistance[t] < now:
                    T.append(t)
                    Pathdistance[t] = now
        Z = T
print( max(Pathdistance))

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N

for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

last = [0] * N
while q != []:
    qn = q.pop(0)
    for v in outs[qn]:
        ins[v] -= 1
        last[v] = max(last[v], last[qn] + 1)
        if ins[v] == 0:
            q.append(v)

print(max(last))

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop(0)
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    now = last[sq] + 1
    for v in outs[sq]:
        last[v] = max(last[v], now)

print(max(last))

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop(0)
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    tp = last[sq] + 1
    for v in outs[sq]:
        last[v] = max(last[v], tp)

print(max(last))

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append((i,0))

last = [0] * N
while q != []:
    qn, d = q.pop(0)
    ins[qn] -= 1
    if ins[qn] > 0:
        continue
    last[i] = d
    for v in outs[qn]:
        q.append((v, d+1))

print(max(last))

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop(0)
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    t = last[sq] + 1
    for v in outs[sq]:
        last[v] = max(last[v], t)

print(max(last))

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(i) for i in input().split()) 

outs = [[] for i in range(N)]
ins = [0] * N


for _ in range(M):
    x, y = (int(i) for i in input().split())
    x -= 1
    y -= 1
    outs[x].append(y)
    ins[y] += 1

q = []
for i in range(N):
    if ins[i] == 0:
        q.append(i)

result = []
while q != []:
    qn = q.pop(0)
    result.append(qn)
    for v in outs[qn]:
        ins[v] -= 1
        if ins[v] == 0:
            q.append(v)


last = [0] * N
# last[i] = iが最後だったときに最長のパス
for sq in result:
    for v in outs[sq]:
        last[v] = max(last[v], last[sq] + 1)

print(max(last))

Submission status: Time Limit Exceeded

Solution code:
import collections

N,M = map(int,input().split())
L = [[False for j in range(N)] for i in range(N)]

for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    L[a][b] = True

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

for i in range(N) :
    q = collections.deque()
    q.append(i)
    dist = [0 for i in range(N)]
    while q :
        now = q.pop()
        for j in range(N) :
            if not L[now][j] :
                continue
            dist[j] = max(dist[j], dist[now]+1)
            if j < i :
                dp[i] = max(dp[i], dist[j] + dp[j])
            else :
                q.append(j)
    dp[i] = max(dp[i], max(dist))

ans = max(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

path = [[False for i in range(N)] for j in range(N)]

not_start = []

for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    not_start.append(b)

not_start = set(not_start)

start = list(set(range(N)).difference(not_start))

ans = 0

for i in range(len(start)) :
    q = collections.deque()
    q.append(start[i])
    dist = [0 for i in range(N)]
    
    while q :
        now = q.pop()
        for j in range(N) :
            if path[now][j] :
                q.append(j)
                dist[j] = max(dist[j], dist[now]+1)
    
    ans = max(ans, max(dist))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

path = [[False for i in range(N)] for j in range(N)]
detect_start = [[False for i in range(N)] for j in range(N)]
for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    detect_start[b][a] = True

start = []
for i in range(N) :
    if not sum(detect_start[i]) :
        start.append(i)

ans = 0

for i in range(len(start)) :
    q = collections.deque()
    q.append(start[i])
    dist = [0 for i in range(N)]
    
    while q :
        now = q.pop()
        for j in range(N) :
            if path[now][j] :
                q.append(j)
                dist[j] = max(dist[j], dist[now]+1)
    
    ans = max(ans, max(dist))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

path = [[False for i in range(N)] for j in range(N)]
detect_start = [[False for i in range(N)] for j in range(N)]
for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    detect_start[b][a] = True

start = []
for i in range(N) :
    for j in range(N) :
        if detect_start[i][j] :
            break
    else :
        start.append(i)

ans = 0

for i in range(len(start)) :
    q = collections.deque()
    q.append(start[i])
    dist = [0 for i in range(N)]
    
    while q :
        now = q.popleft()
        for j in range(N) :
            if path[now][j] :
                q.append(j)
                dist[j] = max(dist[j], dist[now]+1)
    
    ans = max(ans, max(dist))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

path = [[False for i in range(N)] for j in range(N)]
detect_start = [[False for i in range(N)] for j in range(N)]
for i in range(M) :
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    detect_start[b][a] = True

start = []
for i in range(N) :
    for j in range(N) :
        if detect_start[i][j] :
            break
    else :
        start.append(i)

ans = 0

for i in range(len(start)) :
    q = collections.deque()
    q.append(start[i])
    dist = [0 for i in range(N)]
    
    while q :
        now = q.pop()
        for j in range(N) :
            if path[now][j] :
                q.append(j)
                dist[j] = max(dist[j], dist[now]+1)
    
    ans = max(ans, max(dist))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
e=[ set() for _ in range(n+1) ]
c=[0]*(n+1)
s1=set()
s2=set()
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    s1.add(a)
    s2.add(b)
    e[a].add(b) 

s1=s1-s2
# print(s1)
i=0
q=[ list(s1) ]
while q:
    t=[]
    for lst in q:
        for w in lst:
            if e[w]: t.append(e[w])
            c[w]=i
    q=t
    i=i+1

print(i-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
e=[[] for _ in range(n+1)]
c=[0]*(n+1)
s1=set()
s2=set()
for _ in range(m):
    a, b = map(int, input().split())
    s1.add(a)
    s2.add(b)
    e[a].append(b)

s1=s1-s2

for v in s1:
    i=0
    q=e[v]
    while q:
        i=i+1
        t=[]
        for w in q:
            t.extend(e[w])
            if c[w]<i: c[w]=i
        q=t

print(max(c))

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit; setrecursionlimit(10**9)
N, M = map(int, input().split())
edge = {}
starts = set(i for i in range(1, N+1))
for _ in range(M):
    x, y = map(int, input().split())
    if x not in edge:
        edge[x] = [y]
    else:
        edge[x].append(y)
    starts -= {y}

def rec(d, e, dp):
    dp[e] = max(dp[e], d)
    if e not in edge:
        return 0
    for f in edge[e]:
        rec(d+1, f, dp)
    return max(dp)

depth = []
for s in starts:
    depth.append(rec(0, s, [0]*(N+1)))
print(max(depth))

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 

    nex_stack = []
    # p = l.pop()
    for p in l:

        cnt = costs[p]

        for c in childs_list[p]:
            if cnt+1 > costs[c]:
                costs[c] = cnt+1
                # l.append( c ) 
                nex_stack.append(c)
    
    l = nex_stack


print(max(costs))

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 
    p = l.pop()

    
    # costs[p] = max(costs[v_idx], cnt)
    # costs[p] = max(costs[p], costs[ 

    cnt = costs[p]

    for c in childs_list[p]:
        if cnt+1 > costs[c]:
            # l.append(  (c, childs_list[c], cnt+1) ) 
            costs[c] = cnt+1
            l.append( c ) 
            # nex_stack.append( c ) 


print(max(costs))

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

# l = [(i,childs_list[i],0)]
l = [(i,childs_list[i],0) for i in roots]
costs = [ 0 for _ in range(N)]

while l: 
    nex_stack = []

    for p in l:
        v_idx, chlist, cnt = p
        costs[v_idx] = max(costs[v_idx], cnt)

        for c in chlist:
            if cnt+1 > costs[c]:
                # l.append(  (c, childs_list[c], cnt+1) ) 
                nex_stack.append( (c, childs_list[c], cnt+1) ) 

    l = nex_stack
print(max(costs))

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

# l = [(i,childs_list[i],0)]
l = [(i,childs_list[i],0) for i in roots]
costs = [ 0 for _ in range(N)]

while l: 
    v_idx, chlist, cnt = l.pop()
    costs[v_idx] = max(costs[v_idx], cnt)

    for c in chlist:
        if cnt+1 > costs[c]:
            l.append(  (c, childs_list[c], cnt+1) ) 
print(max(costs))

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

dp = [ [N+1]*N for _ in range(N)] 

# dp[i][j], i:step, j:path
from collections import Counter, defaultdict
parents = Counter( x[0] for x in g)
childs  = Counter( x[1] for x in g)


parents_dict = defaultdict(lambda :-1)
childs_list  = defaultdict(list)
parents_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
    parents_dict[y]=x
    parents_list[y].append(x)

# print(parents)
roots = []
for i in range(N):
    # if childs[i] == 0:
    # if len( childs_list[i]) == 0:
    # if parents[i] == 0:
    if childs[i] == 0:
        roots.append(i)

l =  [ (i,childs_list[i], 0) for i in roots]
# l =  [ (i,parents_dict[i], 0) for i in roots]
# print(l)
# exit(0)

costs = [ 0 for _ in range(N)]
ans = 0
while l: 
    # v_idx, pa, cnt = l.pop()
    v_idx, chlist, cnt = l.pop()
    costs[v_idx] = max(costs[v_idx], cnt)
    ans = max(ans, cnt)
    # if parents_dict[pa] != -1:
    for c in chlist:
        if cnt+1 > costs[c]:
            l.append(  (c, childs_list[c], cnt+1) ) 
        # l.append(  (pa, parents_dict[pa], cnt+1) ) 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

dp = [ [N+1]*N for _ in range(N)] 

# dp[i][j], i:step, j:path
from collections import Counter, defaultdict
parents = Counter( x[0] for x in g)
childs  = Counter( x[1] for x in g)


childs_list  = defaultdict(list)
for x,y in g:
    childs_list[x].append(y)


roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

# root = i
l =  [ (i,childs_list[i], 0) for i in roots]
# l = [ (i, childs_list[i], 0) ] 
ans = 0
while l: 
    v_idx, chlist, cnt = l.pop()
    ans = max(ans, cnt)
    for c in sorted(chlist, key=lambda x:childs[x]):
        l.append(  (c, childs_list[c], cnt+1) ) 
print(ans)

Submission status: Time Limit Exceeded

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

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

nl=[ [] for i in range(N+1) ] 
f=[ 0 for i in range(N+1) ]
dp=[ 0 for i in range(N+1) ]

for i in range(M):
	x,y=map(int, sys.stdin.readline().split())
	nl[x].append(y)
	f[y]=1

start=[]
for i in range(1,N+1):
	if f[i]==0:
		start.append(i)


def dfs(v):
	for u in nl[v]:
		dp[u]=max( dp[u], dp[v]+1)
		dfs(u)


for s in start:
	dfs(s)

print max(dp)

Submission status: Time Limit Exceeded

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

edges = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x][y] = 1

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

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for i in range(1, n+1):
        if edges[u][i]:
            d = max(d, 1+longest_path(i))
    dp[u] = d
    return d

for u in range(n+1):
    longest_path(u)

print(max(dp))

Submission status: Time Limit Exceeded

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

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

nl=[ [] for i in range(N+1) ] 
f=[ 0 for i in range(N+1) ]
dp=[ 0 for i in range(N+1) ]

for i in range(M):
	x,y=map(int, raw_input().split())
	nl[x].append(y)
	f[y]=1

start=[]
for i in range(1,N+1):
	if f[i]==0:
		start.append(i)


def dfs(v):
	for u in nl[v]:
		dp[u]=max( dp[u], dp[v]+1)
		dfs(u)


for s in start:
	dfs(s)

print max(dp)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
X = [[] for i in range(N)] # iからの行き先
Y = [[] for i in range(N)] # iに来る元

for i in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    X[x].append(y)
    Y[y].append(x)
    
Z = [0 for i in range(N)] # iまでの最長pathの長さ
L = []
k = 0

L.append([])
for i in range(N):
    if len(Y[i]) == 0:
        L[k].append(i)
        Z[i] = 1

while True:
    k += 1
    L.append([])
    for l in L[k-1]:
        for x in X[l]:
            L[k].append(x)
            Z[x] = k + 1
    
    if len(L[k]) == 0:
        print(k-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
info = [[] for _ in range(N+1)] # i -> info[i] 行き先
note = []
for _ in range(M):
    x,y = map(int,input().split())
    info[x].append(y)
    note.append(y)
note = list(set(range(1,N+1)) - set(note))
ans = 0
def dfs(p, length = 0):
    # 行き場所がなければlengthをメモ
    global ans
    if info[p] == [] and length > ans:
        ans = length
    for d in info[p]:
        dfs(d, length + 1)
for i in note:
    dfs(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
info = [[] for _ in range(N+1)] # i -> info[i] 行き先
note =[]
for _ in range(M):
    x,y = map(int,input().split())
    info[x].append(y)
    note.append(y)
note = list(set(range(1,N+1)) - set(note))
len_list = []
visited_list = []
def visited(p):
    for e in visited_list:
        if e == p:
            return True
    return False
def dfs(p, length = 0):
    # 訪問済みならlength-1をメモ
    if visited(p) is True:
        len_list.append(length-1)
    # 訪問の印を付ける
    visited_list.append(p)
    # 行き場所がなければlengthをメモ
    if info[p] == []:
        len_list.append(length)
    for d in info[p]:
        dfs(d, length + 1)
for i in note:
    dfs(i)
    visited_list.clear()
ans = max(len_list)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
info = [[] for _ in range(N+1)] # i -> info[i] 行き先
note = [[] for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    info[x].append(y)
    note[y].append(x)

len_list = []
visited_list = []
def visited(p):
    for e in visited_list:
        if e == p:
            return True
    return False
def dfs(p, length = 0):
    # 訪問済みならlength-1をメモ
    if visited(p) is True:
        len_list.append(length-1)
    # 訪問の印を付ける
    visited_list.append(p)
    # 行き場所がなければlengthをメモ
    if info[p] == []:
        len_list.append(length)
    for d in info[p]:
        dfs(d, length + 1)
for i in range(1,N+1):
    if note[i] != []:
        continue
    dfs(i)
    visited_list.clear()
ans = max(len_list)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

n,m = map(int, input().split())
edge = [set() for _ in [0]*n]
iny = [0 for _ in [0]*n]
for _ in range(m):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].add(y)
    iny[y] += 1

# from random import randint
# n = 10**1
# m = 10**1
# edge = [set() for _ in [0]*n]
# for _ in range(m):
#     x = randint(0,n-1)
#     y = randint(0,n-1)
#     while x==y:
#         x = randint(0,n-1)
#         y = randint(0,n-1)
#
#     edge[x].add(y)

res = 0
d = [0]*n
for i in [j for j in range(n) if iny[j]==0]:
    if d[i]>0:
        continue
    st = deque([i])
    while len(st)>0:
        s = st.popleft()
        for v in edge[s]:
            if d[v]<d[s]+1:
                d[v] = d[s]+1
                st.append(v)

print(max(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
edge = [set() for _ in [0]*n]
iny = [0 for _ in [0]*n]
for _ in range(m):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].add(y)
    iny[y] += 1

# from random import randint
# n = 10**1
# m = 10**1
# edge = [set() for _ in [0]*n]
# for _ in range(m):
#     x = randint(0,n-1)
#     y = randint(0,n-1)
#     while x==y:
#         x = randint(0,n-1)
#         y = randint(0,n-1)
#
#     edge[x].add(y)

res = 0
d = [0]*n
for i in [j for j in range(n) if iny[j]==0]:
    if d[i]>0:
        continue
    st = [i]
    while len(st)>0:
        s = st.pop()
        for v in edge[s]:
            if d[v]<d[s]+1:
                d[v] = d[s]+1
                st.append(v)

print(max(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
edge = [set() for _ in [0]*n]
for _ in range(m):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].add(y)

res = 0
d = [-1]*n

for i in range(n):
    if d[i]>-1:
        continue
    st = [i]
    d[i] = 0
    while len(st)>0:
        s = st.pop()
        for v in edge[s]:
            if d[v]<d[s]+1:
                d[v] = d[s]+1
                st.append(v)

print(max(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
edge = [set() for _ in [0]*n]
for _ in range(m):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].add(y)

res = 0
d = [-1]*n

for i in range(n):
    if d[i]>-1:
        continue
    st = [i]
    d[i] = 0
    while len(st)>0:
        s = st.pop()
        for v in edge[s]:
            d[v] = max(d[v], d[s]+1)
            st.append(v)

print(max(d))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
edge = [[] for _ in range(n)]
xl = set()
yl = set()
for _ in range(m):
    x,y = map(int, input().split())
    x -= 1
    y -= 1
    edge[x].append(y)
    xl.add(x)
    yl.add(y)

res = 0

for i in xl-yl:
    d = [0 for _ in range(n)]
    st = [i]
    while len(st)>0:
        s = st.pop()
        for v in edge[s]:
            d[v] = max(d[v], d[s]+1)
            st.append(v)
    res = max(res, max(d))

print(res)