//求歐拉回路或歐拉路,鄰接陣形式,復雜度O(n^2)
//返回路徑長度,path返回路徑(有向圖時得到的是反向路徑)
//傳入圖的大小n和鄰接陣mat,不相鄰點邊權0
//可以有自環與重邊,分為無向圖和有向圖

#define MAXN 100

void find_path_u(int n,int mat[][MAXN],int now,int& step,int* path){
	int i;
	for (i=n-1;i>=0;i--)
		while (mat[now][i]){
			mat[now][i]--,mat[i][now]--;
			find_path_u(n,mat,i,step,path);
		}
	path[step++]=now;
}

void find_path_d(int n,int mat[][MAXN],int now,int& step,int* path){
	int i;
	for (i=n-1;i>=0;i--)
		while (mat[now][i]){
			mat[now][i]--;
			find_path_d(n,mat,i,step,path);
		}
	path[step++]=now;
}

int euclid_path(int n,int mat[][MAXN],int start,int* path){
	int ret=0;
	find_path_u(n,mat,start,ret,path);
//	find_path_d(n,mat,start,ret,path);
	return ret;
}