10分求助!
查看原帖
10分求助!
907368
andycode楼主2024/7/7 15:09
#include <bits/stdc++.h>
using namespace std;
int n,m,dist[100005][2];//n为结点数,m为边数,dist[i][0]为点i的入度,dist[i][1]为点i的出度 
vector<int> g[100005],p[100005];//g[i]存储图,pow[i]标记改边是(1)否(0)被遍历 
void dfs(int s,int e,int sum){//sum为前面总共遍历的多少条边 
	cout<<s<<' ';
	if(sum==m-1){
		cout<<e;
		return;
	}
	int minn=n+1,w=0;
	for(int i=0;i<g[s].size();i++)
		if(g[s][i]<minn && !p[s][i])minn=g[s][i],w=i;
	p[s][w]=1;
	dfs(minn,e,sum+1);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);//存储图 
		p[u].push_back(0);//初始化 pos 
		dist[u][1]++,dist[v][0]++;//增加点u的出度,点v的入度 
	}
	int s=0,e=0;//s为起点,e为终点,初始化为0进行判重 
	for(int i=1;i<=n;i++){
		if(dist[i][0]!=dist[i][1]){
			if(abs(dist[i][0]-dist[i][1])>1){//不构成起点或终点 
				cout<<"No";
				return 0;
			}else if(dist[i][0]+1==dist[i][1] && !s)s=i;//起点的出度为入度加1(如果图没有欧拉回路) 
			else if(dist[i][0]+1==dist[i][1] && s){
				cout<<"No";
				return 0;
			}else if(dist[i][1]+1==dist[i][0] && !e)e=i;//终点的入度为出度加1(如果图没有欧拉回路) 
			else if(dist[i][1]+1==dist[i][0] && e){
				cout<<"No";
				return 0;
			}
		}
	}
	if((s && !e) || (!s && e)){
		cout<<"No";
		return 0;
	}else if(!s && !e)s=e=1;
	//如果未找到起点和终点说明所有点的出度和入度相同,有欧拉回路,则取最小的点(1)为起点和终点(因为欧拉回路中起点等于终点)
	dfs(s,e,0);//深搜  
	return 0;
}
2024/7/7 15:09
加载中...