#include <iostream.h>

const int nmax=100;

typedef struct
{
	int data[nmax+1];    
    int adjmat[nmax+1][nmax+1];   
    int n,e;             
}mat_graph;

typedef struct node * pointer;

struct node 
{                 
	int no;                     
	pointer next;                  
};

typedef struct 
{
	int data;                    
	pointer first;
}headtype;                        

typedef struct
{
	headtype adjlist[nmax+1];            
	int n,e;                       
}lk_graph;
                   

int pathdetect (lk_graph *gl,int v);
void main()
{
	mat_graph ga;
	int i,j;
    ga.n=4;
	ga.e=4;
	ga.adjmat[1][2]=1;
	ga.adjmat[2][3]=1;
	ga.adjmat[3][1]=1;
	ga.adjmat[1][4]=1;
	lk_graph gl;
	pointer p;
	gl.n=ga.n;
	gl.e=ga.e;
	for(i=1;i<=gl.n;i++) gl.adjlist[i].first=NULL;
	for(i=1;i<=ga.n;i++)
		for(j=ga.n;j>=i;j--)
		{
			if(ga.adjmat[i][j]==0) continue;
			p=new node;                       
			p->no=j;                          
			p->next=gl.adjlist[i].first;
			gl.adjlist[i].first=p;
		}
	pathdetect(&gl,4);
}

int pathdetect (lk_graph *gl,int v)
{
	int S[nmax];
	int visited[100];
	int top;
	int k;
	pointer p;
	top=-1;
	S[++top]=v;
	do{
		p=gl->adjlist[S[top]].first;
		while (p!=NULL&&visited[p->no]) p=p->next;         
		if (p==NULL)  top--;
		else {
			visited[p->no]=1;
			S[++top]=p->no;
			if(p->no==v) {                             
				cout<<"發現回路：\n";
				for(k=0;k<=top;k++) cout<<S[k]<<" ";
				return 1;
			}
		}
	}while(top!=-1);
	cout<<"沒有回路"<<endl;
	return 0; 
}