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:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion
template <typename T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

map<int, vector<int>> dag;
vector<int> max_depth;
int ans = 0;
void dfs(int v, int d = 0)
{
    chmax(max_depth[v], d);
    chmax(ans, max_depth[v]);
    for (auto &child : dag[v])
    {
        dfs(child, d + 1);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<bool> start(n, true);
    max_depth = vector<int>(n, 0);
    rep(i, m)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        dag[x].push_back(y);
        start[y] = false;
    }

    rep(i, n)
    {
        if (!start[i])
            continue;

        dfs(i);
    }

    cout << ans << endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
from sys import stdin, exit

input = stdin.readline
lmi = lambda: list(map(int, input().split()))
mi = lambda: map(int, input().split())
si = lambda: input().strip('\n')
ssi = lambda: input().strip('\n').split()


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


n, m = mi()
graph= [[] for i in range(n+1)]
for i in range(m):
    a, b = mi()
    graph[a].append(b)
dp = [-1]*(n+1)
for i in range(1, n+1):
    if dp[i] == -1:
        dfs(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
import math
import sys
import collections


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

dp =[-1] * (N + 1)

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


    res = 0
    for nv in di[v]:
        res = max(rec(nv) + 1 ,res)  # × dp[nv] ○ rec(nv) ∵ dp[nv]が未計算の場合があるから
    dp[v] = res
    return res

qs = [ list(map(int,input().split(" "))) for _ in range(M)]

# print(qs)
di = collections.defaultdict(lambda :[])
for q in qs:
    x,y = q
    di[x].append(y)
    #dp[y] → yを終点としたlongest path

for i in range(N + 1):
    rec(i)
print(max(dp))

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def longest_path(n, edges):
    adj_list = defaultdict(list)
    for x, y in edges:  # x -> y
        adj_list[y].append(x)

    distances = [None] * n

    def dfs(x):
        if distances[x] is None:
            if adj_list[x]:
                for y in adj_list[x]:
                    dfs(y)
                distances[x] = max((distances[y] + 1 for y in adj_list[x]))
            else:
                distances[x] = 0

    for x in range(n):
        dfs(x)

    return max(distances)


def main():
    n, m = [int(x) for x in input().split()]
    edges = [None] * m
    for i in range(m):
        edges[i] = [int(x) - 1 for x in input().split()]

    return longest_path(n, edges)


print(main())

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def longest_path(n, edges):
    adj_list = defaultdict(list)
    for x, y in edges:  # x -> y
        adj_list[y].append(x)

    distances = [None] * n

    def dfs(x):
        if distances[x] is None:
            for y in adj_list[x]:
                dfs(y)
            distances[x] = max((distances[y] + 1 for y in adj_list[x]), default=0)

    for x in range(n):
        dfs(x)

    return max(distances)


def main():
    n, m = [int(x) for x in input().split()]
    edges = [None] * m
    for i in range(m):
        edges[i] = [int(x) - 1 for x in input().split()]

    return longest_path(n, edges)


print(main())

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

h = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    h[x-1].append(y-1)

dp = [0]*(N+1)


def dist(v):
    if dp[v] > 0:
        return dp[v]
    dp[v] = 0
    for nv in h[v]:
        dp[v] = max([dp[v], dist(nv)+1])
    return dp[v]


ans = 0
for v in range(N):
    ans = max([ans, dist(v)])

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import os
f = open('../../input.txt', 'r')
sys.stdin = f

from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

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

dp = [-1]*(n+1)
dp[0] = 0

def get_longest(x):
    global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

ans = 0
for i in range(1,n+1):
    ans = max(ans, get_longest(i))

print(ans)

Submission status: Runtime Error

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

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

dp = [-1]*(n+1)
dp[0] = 0

def get_longest(x):
    # global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

ans = 0
for i in range(1,n+1):
    ans = max(ans, get_longest(i))

print(ans)

Submission status: Runtime Error

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

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

dp = [-1]*(n+1)
dp[0] = 0

def get_longest(x):
    global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

ans = 0
for i in range(1,n+1):
    ans = max(ans, get_longest(i))

print(ans)

Submission status: Runtime Error

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

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

dp = [-1]*(n+1)
dp[0] = 0

def get_longest(x):
    global dp

    if( dp[x] > 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

for i in range(1,n+1):
    get_longest(i)

print(max(dp))

Submission status: Runtime Error

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

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

dp = [-1]*(n+1)

def get_longest(x):
    global dp

    if( dp[x] > 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

for i in range(1,n+1):
    get_longest(i)

print(max(dp))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodeToGo = [[] for _ in range(n)]
nodeFrom = [0] * n
ans = [0] * n

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

for i, node in enumerate(nodeFrom):
    if not node == 0:
        continue
    start = [i]
    while start:
        s = start.pop()
        start = list(set(start.extend(nodeToGo[s])))
        for node in nodeToGo[s]:
            ans[node] = max(ans[node], ans[s]+1)

print(max(ans))