Hello,

That's my solution:

1) Use

**Tarjan's strongly connected components algorithm** to find all connected components,

2) If there is any component larger then 1, you have cycle, so your algorithm should return

`cycle found`

,

3) If there isn't, you end up with

**DAG** (

**D**irected

**A**cyclic

**G**raph), so you can find topological order (note: if you correctly implement

**Tarjan's algorithm** you also found needed order), for example using

**DFS algorithm**
4) Then go through your DAG after

*toposorting*, and make use of some

**Dynamic Programming** on DAG (this is which

**DP** stands for). So in each vertex store length of the longest path ending in this vertex. To calculate that length use simple formula iterating through each

`u`

:

`len[v] = max(len[v], len[u] + 1)`

where

`u`

is

`v`

's father.

5) Then the greatest

`len[i]`

(for any

`i`

) is your result!

And this is my c++ code for your problem:

const int N = 1e9; vector<int> digraph[N], transpose[N], postorder; bool visited[N]; int n, m, len[N];
void DFS(int v) {
visited[v] = true;
for (int u : digraph[v])
if (visited[u] == false)
DFS(u);
postorder.push_back(v);
}
void DFS_2(int v) {
visited[v] = true;
for (int u : transpose[v])
if (visited[u] == false)
DFS_2(u);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
digraph[u].push_back(v);
transpose[v].push_back(u);
}
for (int v = 1; v <= n; v++)
if (visited[v] == false)
DFS(v);
reverse(postorder.begin(), postorder.end());
for (int v = 1; v <= n; v++)
visited[v] = false;
int c = 0; for (int v : postorder)
if (visited[v] == false)
c++, DFS_2(v);
if (c < n) cout << "cycle found";
int longest = 0; for (int v : postorder)
for (int u : transpose[v])
len[v] = max(len[v], len[u] + 1);
longest = max(longest, len[v]);
cout << "the longest path in graph: " << longest;
}

In terms of time complexity we've got

`O(n+m)`

(

`n`

is number of nodes and

`m`

is number of edges).

At the very least provide names that are concise enough to be googled, so the reader will be able to look up if it happens to be something he is familiar with under a different name.