404error 404error - 3 months ago 23
C++ Question

Alternative algorithm for depth first search

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

ead ead
Answer

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.

Comments