当前位置: 代码迷 >> 综合 >> 欧拉回路 Codeforces723E One-Way Reform
  详细解决方案

欧拉回路 Codeforces723E One-Way Reform

热度:41   发布时间:2023-12-14 03:05:49.0

传送门:点击打开链接

题意:给你无向图,现在给无向图定向,使得最多的点,入度等于出度。

思路:首先,对于无向图,奇数度的点,肯定是不能使得入度等于出度的。

对于一个有向图欧拉回路,我们可以知道,欧拉回路上所有的点的入度等于出度。

然后,我们还能知道一个性质,对于一个图,度为奇数的个数,一定是偶数。

所以我们把度为奇数的点分成很多组,每组2个点,然后把每组内部的2个点连一条边。

这样的话,整个图,就只有度为偶数的点了。然后我们再跑欧拉回路,就能得到答案了。

能看到这个题想到欧拉回路,这个想法实在是太跳跃了!得打开思维才行。

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;struct Edge {int v, sign, nxt;
} E[MX];
int Head[MX], erear;
void edge_init() {erear = 0;memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v, int sign) {E[erear].v = v;E[erear].sign = sign;E[erear].nxt = Head[u];Head[u] = erear++;
}int n, m;
int IN[MX];
vector<int> one;
bool vis[MX], used[MX];void Fleury(int u) {used[u] = 1;for(int i = Head[u]; ~i; i = Head[u]) {Head[u] = E[i].nxt;if(!vis[i | 1]) {int v = E[i].v;vis[i | 1] = 1;if(E[i].sign) printf("%d %d\n", u, v);Fleury(v);}}
}
int main() {int T; //FIN;scanf("%d", &T);while(T--) {edge_init();scanf("%d%d", &n, &m);memset(vis, 0, sizeof(vis));memset(used, 0, sizeof(used));memset(IN, 0, sizeof(IN));one.clear();for(int i = 1; i <= m; i++) {int u, v;scanf("%d%d", &u, &v);edge_add(u, v, 1);edge_add(v, u, 1);IN[u]++; IN[v]++;}int ans = 0;for(int i = 1; i <= n; i++) {if(IN[i] % 2) one.push_back(i);else ans++;}for(int i = 0; i + 1 < one.size(); i += 2) {int u = one[i], v = one[i + 1];edge_add(u, v, 0);edge_add(v, u, 0);}printf("%d\n", ans);for(int i = 1; i <= n; i++) {if(!used[i]) Fleury(i);}}return 0;
}