图复习

//图的二维数组邻接矩阵存储
int n,e,w;    //定点数和边数 权值 
int g[101][101];
void  make1(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j=+) g[i][j]=0x7fffffff;
	} //初始化
	cin>>e; 
	int x,y;
	for(int i=1;i<=e;i++) {
		cin>>x>>y>>w;
		g[x][y]=w;
		g[y][x]=w; //这是由于无向图，所以有两句 
	}
} 

//邻接表
struct node{
	int from,to,dis;
	node(int a,int b,int c){
		from=a;to=b;dis=c;
	}
}; 
vector<node> adj[maxn];

//数组模拟邻接表
//专业名------链式前向星 
struct Edge{
	int next;  //下一条编的编号 
	int to;    //这条边的去处 
	int dis;   //边的权值 
}edge[1001];                   //这是边 
int head[101],num_edge;        //这是节点 

void add_edge(int from,int to,int dis){  //添加一条从from到to的距离为dis的单向边！ 
	 edge[num_edge].to=to;
	 edge[num_edge].dis=dis;
	 edge[++num_edge].next=head[from];
	 head[from]=num_edge; 
}

void make2(){
	cin>>n>>e;
	num_edge=0;
	int x,y,d;
	for(int i=1;i<=e;i++){
		cin>>x>>y>>d;
		add_edge(x,y,d);
	}
	for(int i=head[1];i!=0;i=edge[i].next){
		//遍历操作 
	}
} 
int main(){
	
return 0;
}

void dfss(int x,int depht){ //带层数的（邻接表版） 
	vis[x]=1;
	for(int i=1;i<=adj[x].size();i++){
		int j=adj[x][i];
		if(vis[j]) dfs(j,depth+1); //不需要判断是不是连接 
	}
}
//广度优先 
struct node{
	int v; //顶点编号
	int layer; //层号 
};
vector<node> ajd[MAXN];
void bfsss(int x,int layer){
	node start;
	start.v=x;  //起始编号
	start.layer=0;
	queue<node> q;
	q.push(start);
	vis[x]=1;
	while(!q.empty()){
		node now=q.front();
		q.pop();
		int u=now.v;
		for(int i=1;i<ajd[u].size();i++){
			node j=adj[u][i]; //相连的顶点
			j.layer=now.layer+1;
			if(vis[j.v]==0){
				q.push(j);
				vis[j.v]=1;
			} 
			
		}
	} 
}

//对整张图进行遍历
//如果图是联通的，那么只需要进行一次遍历了
void travdfs(){
	for(int i=1;i<=n;i++){
		if(vis[i]==0) dfs(i);
	}
} 
void travbfs(){
	for(int i=1;i<=n;i++){
		if(vis[i]==0) bfs(i,1);  //层数 
	}　

int n,e;
int circuit[101],d[101][101],c[101];  //c是每个点的度，用来判断是欧拉路还是欧拉回路 
int num;
void find(int i){
	for(int j=1;j<=n;j++){
		if(d[i][j]==1){
			d[i][j]=d[j][i]=0;  //删除这条边
			find(j); 
		}
	}
	circuit[++num]=i;  //记录路径 
}
//这是欧拉路（2个奇点），欧拉回路（0个奇点） 
int main(){
	cin>>n>>e;
	int x,y;
	memset(c,0,sizeof(c));
	memset(d,0,sizeof(d));
	for(int i=1;i<=e;i++){
		cin>>x>>y;
		d[x][y]=d[y][x]=1;
		c[x]++;
		c[y]++;
	} 
	int start=1;
	for(int i=1;i<=n;i++){
		if(c[i]%2==1) start=i; //从奇点开始 
	}
	num=0;
	find(start);
	for(int i=1;i<=num;i++) cout<<circuit[i]<<" ";
	cout<<endl; 
return 0;
}

//哈密尔顿环：不重复的走过所有的点，并且是回路
//能找出所有的环 
int vi[1001],visted[1001],num[1001],g[1001][1001]; 
int length;
int ans[1001]; //保存答案 
int n,m,x;
void print(){
	for(int i=1;i<length;i++) cout<<ans[i]<<" ";
	cout<<ans[length]<<endl;
}
void dfs(int last,int i){  //上次访问的last,这次的i 
	visted[i]=1;
	vi[i]=1;     //标记 
	for(int j=1;j<=num[i];j++){
		if(g[i][j]==x&&g[i][j]!=last){
			ans[++length]=j;
			print();   //找到一个环，输出 
			length--;
			break; 
		}
		if(!visted[g[i][j]]) dfs(i,g[i][j]);  //遍历所有与i关联的点 
	}
	length--;
	visted[i]=0;  //回溯  不标记vi[]，因为vi表示是否在图中出现过 
} 


int main(){
	memset(visted,0,sizeof(visted));
	memset(vi,0,sizeof(vi));
	cin>>n>>m;
	int y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		g[x][++num[x]]=y;
		g[y][++num[y]]=x;
	}
	for(x=1;x<=n;x++){
		
		if(!vi[x]) {
		length=0;
		dfs(0,x);
		
		}  //以每一个点为起点遍历，因为不是任一个点都可以遍历出环的 
	}
	
return 0;
}