Attempt at solving Kingdom Connectivity problem on InterviewStreet

KingdomConnectivity.cpp

#include <cstdio>
#include <list>
#include <vector>

#define MOD 1000000000
using namespace std;

typedef vector<list<int> > Graph;
enum {WHITE = 0, GREY};

int nPath (const Graph& graph);    

int main (void)
{
    int n, m, i, j, x, y;
    Graph graph;        
    scanf("%d %d", &n, &m); 
    graph.resize(n);
    
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &x, &y);
        graph[x - 1].push_back(y - 1);
    }
    
    int paths = nPath (graph);
    if (paths >= 0)
        printf ("%d\n", paths);
    else
        printf ("INFINITE PATHS\n");
    
    return 0;
}
 

int dfsAcyclicPaths (const Graph& graph, vector<int>& nodes, const int& source, const int& destination)
{
    if (source == destination)
        return 1;

    
    nodes[source] = GREY;
    list<int>::const_iterator iter = graph[source].begin();
    int paths = 0, tmp;   
    bool cycle = false;
    bool inf = false;
    
    while (iter != graph[source].end())
    {
        if (nodes[*iter] == WHITE)
        {
            tmp = dfsAcyclicPaths (graph, nodes, *iter, destination);
            if (tmp >= 0)
            {
                paths = (paths + tmp) % MOD;                
            }
            else
            {
                inf = true;
            }
        }
        else
        {
            cycle = true;
        }
        iter++; 
    }
    
    nodes[source] = WHITE;
//    printf ("%d %d %d %d\n", source, paths, cycle, inf);
    if (inf || (cycle && paths > 0))
        return -1;    
    
    return paths;
}


int nPath(const Graph& graph)
{
    vector<int> nodes(graph.size(), WHITE);
    return dfsAcyclicPaths (graph, nodes, 0, graph.size() - 1);    
}

Thank you so much. This code works. I was searching for it for a long time.