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);    
}

hey rajat i think there is some case missing in your code... may be like if some back edge is found at some node to its ancestor... then in recursion the cycle flag should remain true till we reach the ancestor again....

5 5
1 2
4 2
2 3
3 4
2 5

i tried to modify your solution and it covers that case... but still time limit exceeded... do something man ??

include

include

include

define MOD 1000000000

using namespace std;

typedef vector<list > 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& nodes, const int& source, const int& destination, bool& cycle_ref, int& cycle_st_ref)
{
if (source == destination)
return 1;

nodes[source] = GREY;
list<int>::const_iterator iter = graph[source].begin();
int paths = 0, tmp;
bool inf = false;

while (!inf && iter != graph[source].end())
{
    if (nodes[*iter] == WHITE)
    {
        tmp = dfsAcyclicPaths (graph, nodes, *iter, destination,cycle_ref,cycle_st_ref);
        if (tmp < 0 || tmp > 0 && cycle_ref)
        {
            inf = true;
        }
        else if(tmp > 0)
        {
            paths = (paths + tmp) % MOD;
        }
    }
    else if(cycle_ref == false)
    {
        cycle_ref = true;
        if(paths > 0) inf = true;
        cycle_st_ref = *iter; 
    }
    iter++;
}

nodes[source] = WHITE;
if(cycle_ref && cycle_st_ref == source)
{
    cycle_ref = false;
}

// printf ("%d %d %d %d\n", source, paths, cycle, inf);
if (inf)
return -1;

return paths;

}

int nPath(const Graph& graph)
{
vector nodes(graph.size(), WHITE);
bool cycle = false;
int cycle_start;
return dfsAcyclicPaths (graph, nodes, 0, graph.size() - 1, cycle, cycle_start);
}

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