欧拉回路是简单回路_欧拉回路的充分必要条件

欧拉回路是简单回路_欧拉回路的充分必要条件题目大意就是让你对有向图和无向图分别求欧拉回路非常的模板,但是由于UOJ上毒瘤群众太多了所以你必须加上一个小优化就是每次访问过一个边就把它删掉有点像Dinic的当前弧优化的感觉注意是在dfs完一个节点把当前的边加入到栈里面然后输出的时候为了保证原来的顺序就直接弹栈就好了//Author:dream_maker#includeusingnamespacestd;//————–…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

题目大意

就是让你对有向图和无向图分别求欧拉回路

非常的模板,但是由于UOJ上毒瘤群众太多了

所以你必须加上一个小优化

就是每次访问过一个边就把它删掉

有点像Dinic的当前弧优化的感觉

注意是在dfs完一个节点把当前的边加入到栈里面

然后输出的时候为了保证原来的顺序就直接弹栈就好了

//Author: dream_maker

#include

using namespace std;

//———————————————-

typedef pair pi;

typedef long long ll;

typedef double db;

#define fi first

#define se second

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; –a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

template

void Read(T &x) {

bool w = 1;x = 0;

char c = getchar();

while (!isdigit(c) && c != ‘-‘) c = getchar();

if (c == ‘-‘) w = 0, c = getchar();

while (isdigit(c)) {

x = (x<<1) + (x<<3) + c -‘0’;

c = getchar();

}

if (!w) x = -x;

}

template

void Write(T x) {

if (x < 0) {

putchar(‘-‘);

x = -x;

}

if (x > 9) Write(x / 10);

putchar(x % 10 + ‘0’);

}

//———————————————-

const int N = 4e5 + 10;

struct Edge {

int v, id, nxt;

} E[N];

int head[N], tot = 0;

int fro[N], to[N], n, m;

void addedge(int u, int v, int id) {

E[++tot] = (Edge) {v, id, head[u]};

head[u] = tot;

}

namespace Solve1 {

int du[N], vis[N];

stack st;

void dfs(int u) {

for (int &i = head[u]; i; i = E[i].nxt) {

int cur = i;

if (vis[abs(E[cur].id)]) continue;

vis[abs(E[cur].id)] = 1;

dfs(E[cur].v);

st.push(E[cur].id);

}

}

void solve() {

fu(i, 1, m) ++du[fro[i]], ++du[to[i]];

fu(i, 1, n) if (du[i] & 1) {

printf(“NO”);

return;

}

fu(i, 1, m) {

addedge(fro[i], to[i], i);

addedge(to[i], fro[i], -i);

}

fd(i, n, 1) {

if (head[i]) {

dfs(i);

break;

}

}

if ((signed) st.size() != m) {

printf(“NO”);

} else {

printf(“YES\n”);

while (st.size()) {

Write(st.top()), putchar(‘ ‘);

st.pop();

}

}

}

}

namespace Solve2 {

int in[N], out[N], vis[N];

stack st;

void dfs(int u) {

for (int &i = head[u]; i; i = E[i].nxt) {

int cur = i;

if (vis[E[cur].id]) continue;

vis[E[cur].id] = 1;

dfs(E[cur].v);

st.push(E[cur].id);

}

}

void solve() {

fu(i, 1, m) ++out[fro[i]], ++in[to[i]];

fu(i, 1, n) if (out[i] ^ in[i]) {

printf(“NO”);

return;

}

fu(i, 1, m) addedge(fro[i], to[i], i);

fu(i, 1, n) {

if (head[i]) {

dfs(i);

break;

}

}

if ((signed) st.size() != m) {

printf(“NO”);

} else {

printf(“YES\n”);

while (st.size()) {

Write(st.top()), putchar(‘ ‘);

st.pop();

}

}

}

}

int main() {

#ifdef dream_maker

freopen(“input.txt”, “r”, stdin);

#endif

int op; Read(op);

Read(n), Read(m);

fu(i, 1, m) Read(fro[i]), Read(to[i]);

if (op == 1) Solve1::solve();

else Solve2::solve();

return 0;

}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/215512.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号