Detection of Cycle in graph ( wrong output )

[tushu]

int main()
{

char line[100];
int N = 5;
vector<int>adj[N];
FILE *in = fopen("test.txt", "r");

for (int i = 1; i <= N; i++) // reading input from file
{
    fgets(line, 100, in);

    char *pch = strtok(line, "\t \n");
    int u = atoi(pch);

    pch = strtok(NULL, "\t \n");
    while (pch != NULL)
    {
        int v = atoi(pch);
        adj[u-1].push_back(v);
        pch = strtok(NULL, "\t \n");
    }

}
    for( int i = 0; i < 5; i++ ) // printing the graph
    {
       for( int p = 0 ; p < adj[i].size(); p++ )
       {
            cout<< i << " , "<< adj[i][p]<<endl;
       }
    }

    if (isCycle(adj))
         cout << endl << "graph contains cycle" ;
    else
         cout << endl << "graph  does not contain cycle" ;

    return 0;
}

int isCycle( vector<int> adj[] ) 
{
     // Allocate memory for creating V subsets
    int *parent = (int*) malloc( 5 * sizeof(int) ); 
       // Initialize all subsets as single element sets
    memset(parent, -1, sizeof(int) * 5);
    for(int i = 0; i < 5; i++)
    {
       for( int p = 0 ; p < adj[i].size(); p++ )
       {    
            int x = find(parent,i);
            int y = find(parent, adj[i][p]-1);  // I think problem is here

            if (x == y)
            return 1;

        Union(parent, x, y);
        }
    }
    return 0;
}

// A utility function to find the subset of an element i
int find(int parent[], int i)
{    
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

// A utility function to do union of two subsets
void Union(int parent[], int x, int y)
{
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

[tushu]

test.txt file contains following inputs :

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

First column contains the vertices ( 1 - 5 )

1 2 3
Above row ( first row ) means , Node 1 is connected to Node 2 and Node 3

2 1 4 5
Above row ( 2nd row ) means , Node 2 is connected to Node 1 , Node 4 and Node 5

Now here problem is take any input it always says : Graphs contains cycle.( Though graph does not contain cycle )
Now in above input graph does not contain cycle but saying graph contains cycle.
Help please.

[doug4]

Now here problem is take any input it always says : Graphs contains cycle.( Though graph does not contain cycle )
Now in above input graph does not contain cycle but saying graph contains cycle.
Help please.

Assuming you are defining a directed graph, your data does contain a cycle. Actually, a number of them.

1->2->1
1->3->1
2->4->2
2->5->2

By the way, a few comments in your code about what you are trying to do would make it easier to review and comment on your code. You have a lot going on here that is not obviously apparent. Many of us are too busy to spend lots of time working through obtuse code to try to figure out what it's supposed to be doing. Give us a hand and leave some bread crumbs for us.

Also, this is C++, so there is no reason to call malloc. Another vector would be great here, or at least use c++'s new and delete. (And you never called free, so you have a memory leak.)

[tushu]

@doug4 :
I tried to write comments wherever possible.
I know I should have used "new" instead of malloc , sorry for that.
You just focus on isCycle() function. Rest will be right as I have tested those codes on other program.
Upto isCycle () is just reading the graph from input file and printing it. That is correct code as I am reading and printing correct data.
Only isCycle () function has something wrong.

[doug4]

You just focus on isCycle() function. Rest will be right as I have tested those codes on other program.
Upto isCycle () is just reading the graph from input file and printing it. That is correct code as I am reading and printing correct data.
Only isCycle () function has something wrong.

Here's the thing. I'm not sure what you are actually trying to do in isCycle. I don't know how the parent array is used and what -1 indicates. That's what you need to comment. I could spend a half an hour trying to figure out what you are trying to do, or I can get back to my work.

This is as good a time as any to invite you to learn to use your debugger. Adding breakpoints and checking values of variables will show you exactly what's going on. You can do that more quickly than I can try to analyze what you have written.

Also, remember that you do have 4 loops in your input data. So, maybe you have a problem with your graph representation, not your code. The debugger will clue you in.