1126.md

1126

• 1126 Eulerian Path (25 point(s))
• 注意图的连通性

#include <iostream>
#include <map>
#include <set>
using namespace std;

map<int, set<int>> mp;
int vis[500 + 5] = { 0 };
int cnt = 0;

void dfs(int i) {
	cnt++;
	vis[i] = 1;
	for (auto it : mp[i]) {
		if (!vis[it]) {
			dfs(it);
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	for (int m = 0; m < M; m++) {
		int a, b;
		cin >> a >> b;
		mp[a].insert(b);
		mp[b].insert(a);
	}
	int num = 0;
	for (int i = 1; i <= N; i++) {
		cout << mp[i].size();
		if (i < N) {
			cout << " ";
		}
		if (mp[i].size() % 2) {
			num++;
		}
	}
	cout << endl;
	dfs(1);
	if (cnt == N && num == 0) {
		cout << "Eulerian" << endl;
	}
	else if (cnt == N && num == 2) {
		cout << "Semi-Eulerian" << endl;
	}
	else {
		cout << "Non-Eulerian" << endl;
	}
}

/*
Sample Input 1:
7 12
5 7
1 2
1 3
2 3
2 4
3 4
5 2
7 6
6 3
4 5
6 4
5 6
Sample Output 1:
2 4 4 4 4 4 2
Eulerian
Sample Input 2:
6 10
1 2
1 3
2 3
2 4
3 4
5 2
6 3
4 5
6 4
5 6
Sample Output 2:
2 4 4 4 3 3
Semi-Eulerian
Sample Input 3:
5 8
1 2
2 5
5 4
4 1
1 3
3 2
3 4
5 3
Sample Output 3:
3 3 4 3 3
Non-Eulerian
*/

References

• PAT 1126. Eulerian Path (25)-甲级