Iterator::Begin() function error

Question

I am trying to learn programming. Was trying to solve a Job schedulling problem using Topological sort in C++. but I am not getting proper o/p. Please assist.

Code:

#include<iostream>
#include<conio.h>
#include<stack>
#include<list>
using namespace std;
int V,E;
list<int> *adj;

void topologicalSort(int v,bool visited[],stack<int> &s)
{
    visited[v] = true;

    list<int>::iterator i;
    for(i = adj[v].begin();i != adj[v].end();++i)// Iterating through the adj list for all nodes
        if(!visited[*i])// If node not visited call again
            topologicalSort(*i,visited,s);
    s.push(v);
}

void main()
{
    int T_case,u,v;
    bool *visited;
    stack<int> s;
    cin>>T_case;
    for(int T = 1; T<=T_case; T++)
    {
        cin>>V>>E;
        adj = new list<int>[V];
        visited = new bool[V];
        for(int e = 1; e <= E; e++)
        {
            cin>>u>>v;
            adj[u].push_back(v);
        }

        for(int i=1;i<=V;i++)
            visited[i] = false;


        for(int i=1;i<=V;i++)
        {
            if(visited[i] == false)
                topologicalSort(i,visited,s);// Recurvivelly calling Topological sort for all nodes.
        }
        //cout<<s.size()<<endl;
        while(s.empty() == false)
        {
            cout<<s.top()<<" ";
            s.pop();
        }

    }
    getch();
    return;
}

Test Case: 1 5 4 <--- Verex Edge 1 2 2 3 4 1 1 5<--- List of edges.

Issue:
O/p getting is 4 1 2 3
where as actual answer should be 4 1 5 2 3.

My program is breaking at line for(i = adj[v].begin();i != adj[v].end();++i) when trying to process node 5. I am not clear why Iterator.begin() function is dumping.

Will really appreciate any kind of help. Thanks in Advance.

Answer 1

Arrays in C++ language are indexed from 0. If you created an array with T *p = new T[N], you are allowed to access elements from p[0] to p[N - 1]. You are not allowed to access p[N]. It does not exist.

Meanwhile, in your code you seem to be assuming that arrays are indexed from 1 to N. This is evident in the following cycles, for example

    for(int i=1;i<=V;i++)
        visited[i] = false;

    for(int i=1;i<=V;i++)
    {
        if(visited[i] == false)
            topologicalSort(i,visited,s);
    }

where visited was allocated as visited = new bool[V]. This is obviously incorrect.