edgedisjointcycles

Edge Disjoint Cycles. You are given an input graph that is either directed or undirected. Write a pr

Edge Disjoint Cycles. You are given an input graph that is either directed or undirected. Write a program 
that reads in a vertex number and lists the number of edge disjoint cycles that start and end at this 
vertex. The output should also list the edges in each of the cycle discovered. Input will be the adjacency
 matrix preceded by a 0 or 1 representing Directed or Undirected graphs respectively.

 
 solution
 
 #include<stdio.h>
#include<stdlib.h>

struct Stk
{
int* q;
int top;
};

struct Node
{
int sz;
struct Stk *st;
struct Node *next;
};

struct Stk *st=NULL;
struct Node *nd = NULL;
struct Node *head = NULL;

void push(int i, int n)
{
/*printf("inside push %d \n",i);*/
if(isempty()==-1)
{
st->q= (int*)malloc(sizeof(int)*n);

}
st->top++;
st->q[st->top]=i;
}

int pop()
{

int res;
/*printf("inside pop ");;*/
if(isempty()==-1)
{
return -1;
}
res = st->q[st->top];
/*printf("%d\n",res);*/
st->top--;
return res;

}

int isempty()
{
if(st->top==-1)
return -1;
else
return 0;
}

void copyStk(struct Stk* t, struct Stk* st, int n)
{
int i;
/*printf("inside copystk\n");*/


t->q = (int*)malloc(sizeof(int)*n);
for(i=0;i<=st->top;i++)
{
t->q[i]=st->q[i];
}
t->top= st->top;
/*printf("t->top is %d\n",t->top);*/
}
void printq(int n )
{
int i,setval,cnt;
struct Node* nd1;
struct Node* prev;

prev= NULL;
nd1=NULL;

setval=0;
if (nd==NULL)
{
/*printf("inside if printq\n");*/
nd=(struct Node*)malloc(sizeof(struct Node));
head = nd;
/*printf("st->top is %d\n",st->top);*/
nd->sz = (st->top)+1;
/*nd->st = st;*/
nd->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd->st,st,n);
/*printf("nd->st->top is %d\n",nd->st->top);*/
}
else
{
/*printf("inside else printq\n");*/
nd = head;
cnt = st->top;
/*printf("cnt is %d\n",cnt);*/
prev = head;
while(nd != NULL)
{
if(cnt < nd->sz)
{
nd1 = (struct Node*)malloc(sizeof(struct Node));
nd1->sz = st->top+1;
/*printf("st->top is %d\n",st->top);*/
/*nd1->st = st;*/
nd1->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd1->st,st,n);
nd1->next = nd;

if(head==nd)
head = nd1;
else
prev->next=nd1;

setval=1;
break;
}
if(cnt>=nd->sz)
{
prev=nd;
nd = nd->next;
}
}

if(setval==0)
{
/*printf("inside setval printq\n");*/
nd1 = (struct Node*)malloc(sizeof(struct Node));
nd1->sz = st->top+1;
printf("st->top is %d\n",st->top);
/*nd1->st = st;*/
nd1->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd1->st,st,n);
prev->next=nd1;
}


}


}

/*void reset(int arr[][3],int n)*/
void reset(int** arr,int n)
{
int i,j;
i=j=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(arr[i][j]==-1)
arr[i][j]=1;
}

}
free(st->q);
st->top=-1;
head=NULL;
nd = NULL;
}

/*int dfs(int src,int dest, int arr[][3], int n, int cnt)*/
int dfs(int src,int dest, int** arr, int n, int cnt, int isdirected)
{
int i,cnt1;


for(i=0;i<n;i++)
{

if(arr[src][i]==1)
{
push(i,n);

arr[src][i]=-1;
if(isdirected ==1)
arr[i][src]=-1;
if(i==dest)
{
cnt++;
/*printf("%d\n",cnt); */
printq(n);
return cnt;
}
else
cnt1 = dfs(i,dest,arr,n,cnt,isdirected);

if(cnt1>cnt)
{
cnt =cnt1;
break;
}
pop();
}
}
return cnt;


}

int main()
{
int notestcases;
int src,dest, i,j,n,cnt;
int** arr;
int* srcArr;
int* destArr;
int isdirected;
/*int arr[][3] = {{0,1,1},{0,0,1},{0,0,0}};*/
i=0;j=0;

st= (struct Stk *)malloc(sizeof(struct Stk));
st->top=-1;
scanf("%d",&isdirected);
scanf("%d",&n);
getchar();
if(n > 0)
{
arr = (int**) malloc(sizeof(int*)*(n));


for(i=0;i<n+1;i++)
arr[i]=(int*)malloc(sizeof(int)*(n));


for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{

scanf("%d",&arr[i][j]);

}

}





i=0;


scanf("%d",&src);

cnt = 0 ;

src = src--;

push(src,n);
cnt  = dfs(src,src,arr,n,0,isdirected);

printf("%d\n",cnt);
nd = head;
while(nd != NULL)
{

for(i=0;i<=nd->st->top;i++)
{
printf("%d",(nd->st->q[i])+1);
if(i < nd->st->top)
printf("->");
}
printf("\n");

nd=nd->next;
}


/*reset(arr,n);*/



/*if notestcases>0*/
}/*if n>0*/

return 0;
}