#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 i,int j);
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,1,2);
}

int pathdetect (lk_graph *gl,int i,int j)
{
	int S[nmax];
	pointer p;
	int top=-1;
	int k;
	int visited[100];
	visited[i]=1;
	S[++top]=i;
		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==j)
					{                     
						cout<<"發(fā)現(xiàn)路徑:"<<endl;
						for(k=0;k<=top;k++)  
							cout<<S[k]<<" ";
						return 1;
					}
				}
		}while(top!=-1);
	
	cout<<"沒有路徑"<<endl;
	return 0;
}