404error - 1 year ago 108

C++ Question

A problem involves a depth first search in a directed graph to find all the nodes that can be reached from a particular node. The solution given below is giving a wrong result on codechef. But I cannot find any test case for which this might produce a different result that the usual dfs algo would.

I know I can directly implement the correct algo to get the right result but I want to learn why my solution was incorrect so that I won't repeat it in future. Please help me identify whats wrong with this solution. The code is commented to explain my approach

`#include <iostream>`

#include <algorithm>

#include <vector>

using namespace std;

typedef long long int lli;

vector <lli> g[1000+5]; // the adjacency list 1 indexed

void dfs(lli j, lli i);

int main(){

lli n, m, k, a, b;

// n = number of nodes

// m = number of relations

// k = multiplication factor

cin >> n >> m >> k;

while(m--){

// a,b means a is dependent upon b (directed graph)

cin >> a >> b;

g[a].push_back(b);

}

for(lli j = 1; j <= n; j++)

for(lli i = 0; i < g[j].size(); i++){

dfs(j, g[j][i]); // adds dependencies of g[j][i]

// to adjacency list of j

}

// ans is the minimum no of nodes dependent on a particular node

lli ans = g[1].size();

for(lli i = 1; i <= n; i++){

if(g[i].size() < ans)

ans = g[i].size();

}

cout << (ans+1)*k <<"\n";

}

void dfs(lli j, lli i){

// adding dependencies of a node to itself

// would result in an infinite loop?

if(i != j){

for(lli k = 0; k < g[i].size(); k++){

// a node is not dependent on itself

if(g[i][k]!=j && find(g[j].begin(), g[j].end(), g[i][k])==g[j].end()){

g[j].push_back(g[i][k]);

dfs(j, g[i][k]);

}

}

}

}`

The link for the problem : problem

link for correct solution: correct solution

Answer Source

Your problem is that you are not aware of multi-edges which are possible with the given problem constrains, otherwise it looks correct. Take a look at this test case:

```
2 4 1
1 2
1 2
2 1
2 1
```

Your program will return 3, but there are only 2 vertices!

Having said that, I would like to add, that I disagree with the sample solution: It says the running time would be `O(N^2)`

which is not true, because it starts `N`

dfs every one with costs of `O(N+M)`

thus resulting in `O(N*(N+M))`

with `N=10^3`

and `M=10^6`

there is no change to be in the time limit of 0.01 seconds!

Actually, this problem can be solved in `O(N+M)`

using algorithms for detecting strongly connected components.