只有90分,根据第一篇题解写的,感觉是输出NO的条件没写对
查看原帖
只有90分,根据第一篇题解写的,感觉是输出NO的条件没写对
1140371
ruanertanjing楼主2024/5/11 16:29

//欧拉路径:只经过一次的边
//欧拉回路:经过欧拉路径能回到起点的回路
//欧拉图:有欧拉 回路 的图
//半欧拉图:有欧拉 路径 的图,但是没有欧拉 回路

//判断是否有欧拉路径:
/*
1、有向图
欧拉路径:
只有两个点出度不等于入度:起点(出度 = 入度 + 1),终点(入度 = 出度 + 1)
其他点:入度 = 出度
欧拉回路:
所有点入度等于出度

2、无向图
欧拉路径:
只有两个点的度数为奇数:起点(出度 = 入度 + 1),终点(入度 = 出度 + 1)
其他点:度数为偶数
欧拉回路:
所有点度数为偶数
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
const int M = 2e5 + 5;

//用Dij不好排序,用vector的图
//struct EDGE
//{
//	int v;
//	int w;
//	int next;
//}EDGE[M];
//
//int head[N];
//int ans[N];
//int vis[N];
//int cnt;
//
//int du[N][2];//入度,出度
//
//void add(int u, int v, int w)
//{
//	cnt++;
//	EDGE[cnt].v = v;
//	EDGE[cnt].w = w;
//	EDGE[cnt].next = head[u];
//	head[u] = cnt;
//}

vector<int>G[N];
stack<int>st;
int du[N][2];//入度,出度
int cnt[2];//记录多少点出度不等于入度,cnt[0]:入度 > 出度,cnt[1]:出度 > 入度
int beginn[N];//记录每个点遍历到了哪个出边

void DFS(int qi)
{
	for (int i = beginn[qi]; i < G[qi].size(); i = beginn[qi]/*注意不是i++,因为经过DFS后,beginn[qi]的值可能早已改变,不能再从目前点的后一个点继续走*/)
	{
		beginn[qi] = i + 1;
		DFS(G[qi][i]);
	}
	st.push(qi);
	//最后放:因为栈是先进后出,要先把该点的出边都遍历完再放入该点,以便输出时该点先输出
}

int main()
{
	int n, m;
	cin >> n >> m;
	int u, v;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v;
		G[u].push_back(v);
		du[u][1]++;
		du[v][0]++;
	}

	int qi = 1;//起点
	//int flag = 0;//flag = 0表示:所有点入度 = 出度
	for (int i = 1; i <= n; i++)
	{
		sort(G[i].begin(), G[i].end());//注意vector和数组对sort的用法不同
		
		if (du[i][0] != du[i][1])
		{
			//flag = 1;
			if (du[i][0] - du[i][1] == 1)//入度 - 出度 = 1:终点
			{
				cnt[1]++;
			}
			else if (du[i][1] - du[i][0] == 1)//出度 - 入度 = 1:起点
			{
				cnt[0]++;
				qi = i;
			}
			else
			{
				cout << "NO" << endl;
				return 0;
			}
		}
	}

	if (cnt[0] != 0 && cnt[0] != cnt[1]/*起点数目不等于终点*/)
	{
		cout << "NO" << endl;
		return 0;
	}

	if (cnt[0] != 0/*不是欧拉回路*/ && cnt[0] != 1/*起点数目不等于1*/)
	{
		cout << "NO" << endl;
		return 0;
	}

	DFS(qi);

	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	return 0;
}
2024/5/11 16:29
加载中...