CodeForces - 788B Weird journey 欧拉路

题意：给定n个点，m条边，问能否找到多少条符合条件的路径。需要满足的条件：1.经过m-2条边两次，剩下两条边1次 2.任何两条路的终点和起点不能相同。

欧拉路的条件：存在两个或者0个奇度顶点。

思路：首先把给每条边都再增加一条边，所有点的度数都是偶数。每条边分为普通边和自环边。

1.删去两条没有公共顶点的普通边，会有四个点的度数变成奇数，不符合欧拉路。

2.删去两条有公共顶点的普通边，会有两个点的度数成为奇数，符合

2.删去一个自环边和一个普通边，会有两个点的度数成为奇数，符合

4.删去两条自环边，所有顶点的度数全是偶数，符合

在此之前必须保证所有的边是连通的，否则根本不可能走完所有的边。判断连通性可用dfs或者并查集。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 1e6 + 5;
vector<int>G[maxn];
int n, m;
int vis[maxn], mark[maxn];
void dfs(int u) {
	vis[u] = 1;
	for(int i = 0; i < G[u].size(); ++i) {
		int v = G[u][i];
		if(!vis[v]) dfs(v);
	}
}
int main() {
	while(scanf("%d%d", &n, &m) == 2) {
		for(int i = 1; i <= n; ++i) G[i].clear();
		memset(mark, 0, sizeof(mark));
		int x, y, loop = 0;
		for(int i = 0; i < m; ++i) {
			scanf("%d%d", &x, &y);
			if(x != y) {
				G[x].push_back(y);
				G[y].push_back(x);
			}
			else {
				++loop;
				mark[x] = 1;
				G[x].push_back(y); //自环
			}
		}
		memset(vis, 0, sizeof(vis));
		for(int i = 1; i <= n; ++i) {
			if(G[i].size()) {
				dfs(i);
				break;
			}
		}
		//是否所有边已经连通
		for(int i = 1; i <= n; ++i) {
			if(G[i].size() && !vis[i]) { //不连通
				printf("0\n");
				return 0;
			}
		}
		LL ans = 0;
		//相邻普通边
		for(int i = 1; i <= n; ++i) {
			int f = G[i].size();
			if(f) {
				if(mark[i]) --f; //减去自环边
				ans += (LL)f * (f-1) / 2;
			}
		}
		ans += (LL)loop * (m-loop); //自环和普通边
		ans += (LL)loop * (loop-1) / 2; //两条自环边
		printf("%lld\n", ans);
	}
	return 0;
}

如有不当之处欢迎指出！

巴特西

CodeForces - 788B Weird journey 欧拉路

最新文章

热门文章