I am trying to run dfs and storing the parent of a child whenever i am finding a longer path to it by using depth but it is giving wrong answers on four test cases which are quiet big to test. I came to know about the toposort and dp solution but I don't understand why doing it this way is wrong. Can anyone tell why this approach is failing or any test case where this approach will fail ?
void dfs(int i, vector<vector<int>> &g, vector<bool> &vis, vector<int> &depth,
vector<int> &par) {
vis[i] = 1;
for (auto child : g[i]) {
if (depth[child] < depth[i] + 1) {
depth[child] = depth[i] + 1;
par[child] = i;
}
if (!vis[child]) dfs(child, g, vis, depth, par);
}
}
vector<int> depth(n, 0), par(n, -1);
vector<bool> vis(n, 0);
dfs(0, g, vis, depth, par);
if (par[n - 1] == -1)
cout << "IMPOSSIBLE\n" << endl;
else {
int x = n — 1;
vector<int> ans;
while (x != -1) {
ans.push_back(x);
x = par[x];
}
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
for(auto i : ans) {
cout << i + 1 << ' ';
}
cout << endl;
}
Here is a test
The main issue is when you do dfs here, you visit node 3 first and update the depth of node 4 to be 2, then it's marked as visited
But you can achieve better depth for node 4 (path: 1->2->5->6->4) but since 4 is already visited you don't visit it again to update the depth of 7 for that path, so your code outputs the path of (1->2->5->6->7) instead of (1->2->5->6->4->7)