1126 Eulerian Path (25分)/图的遍历

题目描述

题目大意

看着题目很长，其实题意很简单：
如果一个连通图的所有结点的度都是偶数，那么它就是Eulerian，如果除了两个结点的度是奇数其他都是偶数，那么它就是Semi-Eulerian，否则就是Non-Eulerian.

入坑

开始把问题想得太简单了，以为只需要判断各个顶点的度就行了，然后还以为只要图的每个顶点的度都不为0就是连通了…其实还是得用搜索算法遍历一遍才知道图是否连通。虽然这样也通过了很多测试点（只有一个没有通过）~

AC代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int>> adj;
bool vis[505];
int num=0;
void dfs(int u) {
	vis[u] = true; num++;
	for (int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i];
		if (vis[v] == 0) dfs(v);
	}
}
int main() {
	//freopen("1.txt", "r", stdin);
	int n, m; cin >> n >> m;
	adj.resize(n + 1);
	while(m--) {
		int c1, c2;
		scanf("%d%d", &c1, &c2);
		adj[c1].push_back(c2);
		adj[c2].push_back(c1);
	}
	dfs(1);
	int oddnum = 0;
	for (int i = 1; i <= n; i++) {
		if (i != 1) cout << " ";
		printf("%d", adj[i].size());
		if (adj[i].size() % 2 == 1) oddnum++;
	}
	cout << endl;
	if (num < n) printf("Non-Eulerian");
	else {
		if (oddnum == 0) printf("Eulerian");
		else if (oddnum == 2) printf("Semi-Eulerian");
		else printf("Non-Eulerian");
	}
	return 0;
}