CODEWITHSUNDEEP
c++algorithmdynamic-programmingdepth-first-search
Siddharth
Siddharth

Reputation: 71

SPOJ KFSTB - Help the Commander in Chief: Wrong Answer

The problem statement asks to find the number of paths from a given source node to a destination node in a directed acyclic graph.

I'm trying to implement this using dfs with dp for optimization. I've tried several small test cases for which the code seems to work fine. I think the problem is with large test cases but I do not know how to test on them. As the number of paths can be very large we're to use modulo. My code is as follows:

#include<iostream>
#include<vector>
#define MOD 1000000007
using namespace std;

typedef vector<long long int> vi;
typedef vector<vi> vii;

vii graph;
vi memo;

long long int dfs(int u, int t)
    {
        if(u==t)
            return 1;
        if((memo[u]%MOD)>0)
            return memo[u]%MOD;

        for(int i=0;i<(int)graph[u].size();i++)
        {
            long long int count = (dfs(graph[u][i], t))%MOD;
            memo[graph[u][i]] = (memo[graph[u][i]]%MOD + count%MOD)%MOD;
            cur_count = (cur_count%MOD + count%MOD)%MOD;
        }
        return cur_count%MOD;
    }

int main()
{
    int d, c, b , s, t, i, a1, a2;
    cin>>d;

    while(d--)
    {
        cin>>c>>b>>s>>t;

        graph.assign(c+1,vi());

        for(i=1;i<=b;i++)
        {
            cin>>a1>>a2;
            graph[a1].push_back(a2);
        }

        memo.assign(c+1, 0);
        memo[s] = dfs(s, t)%MOD;

        cout<<memo[s]<<endl;
    }   
    return 0;
}

In the function dfs: The array memo[] for an element "i" is used for memoization to remember number of paths possible to the destination from the "i"th node. count variable gets the number of paths for current node being visited i.e. "i" and cur_count gets the total paths from all the nodes directly connected to the node "u"

It would be really helpful if I could get some tips or pointers.

Link to the original problem is here: http://www.spoj.com/problems/KFSTB/

Upvotes: 0

Views: 612

Answers (1)

shole
shole

Reputation: 4084

As you are asking for some "tips", here's some:

  1. Keywords: DAG
  2. No self-loop / multiple edge cases
  3. Not really about the I/O format this time (Space, line feed, etc)
  4. Re-Initialize for every test case!! (esp. for STL stuff like vector<>)
  5. Long Long
  6. Think backward: from destination to starting point

Ask for more if you still get stuck :)

Upvotes: 1

Related Questions