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 (
Directed
Acyclic
Graph), 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).