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

欧拉回路是简单回路_欧拉回路的充分必要条件题目大意就是让你对有向图和无向图分别求欧拉回路非常的模板,但是由于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)


相关推荐

  • 帝国时代之国家崛起_崛起于帝国时代

    帝国时代之国家崛起_崛起于帝国时代01关系数据库帝国现在是公元2009年,关系帝国已经统治了我们30多年,实在是太久了。1970年,科德提出关系模型,1974年张伯伦和博伊斯制造出了SQL,帝国迅速建立起了统治。从北美到…

  • murmurhash算法_shell dash使用数组

    murmurhash算法_shell dash使用数组MurmurHash 是一种非加密型哈希函数,适用于一般的哈希检索操作。[1][2][3] 由AustinAppleby在2008年发明,[4][5] 并出现了多个变种,[6] 都已经发布到了公有领域(publicdomain)。与其它流行的哈希函数相比,对于规律性较强的key,MurmurHash的随机分布特征表现更良好

    2022年10月19日
  • shiro安全框架面试题_java分布式锁面试题

    shiro安全框架面试题_java分布式锁面试题shiro安全框架1.shiro可以完成哪些工作?shiro可以帮助我们完成:认证、授权、加密、会话管理、与Web集成、缓存等2.ApacheShiro的三大核心组件a、Subject:当前用户的操作b、SecurityManager:用于管理所有的Subjectc、Realms:用于进行权限信息的验证3.shiro有哪些组件?a、Authentication:身份认证/登录,验证用户是不是拥有相应的身份;b、Authorization:授权,即权限验证,验证某.

    2022年10月14日
  • 深度学习笔记三:反向传播(backpropagation)算法[通俗易懂]

    深度学习笔记三:反向传播(backpropagation)算法[通俗易懂]接上一篇的最后,我们要训练多层网络的时候,最后关键的部分就是求梯度啦。纯数学方法几乎是不可能的,那么反向传播算法就是用来求梯度的,用了一个很巧妙的方法。反向传播算法应该是神经网络最基本最需要弄懂的方法了,要是反向传播方法不懂,后面基本上进行不下去。非常推荐的是Howthebackpropagationalgorithmworks在最开始的博客中提过,这本书是这篇笔记用到的教材之

  • 普通最小二乘法_普通最小二乘法的基本原理

    普通最小二乘法_普通最小二乘法的基本原理简单介绍sklearn中的LinearRegression类拟合了一个带有系数w=(w1,w2,…,wp)w=(w1,w2,…,wp)w=(w_1,w_2,…,w_p)的线形模型,使得数据集实际观测数据和预测数据之间的残差平方和最小:minw||Xw−y||22minw||Xw−y||22min_w||Xw-y||^2_2其中向量w=(w1,w2,…,wp)w=(w1,…

  • 安卓7.0以上安装fiddler证书(模拟器)

    安卓7.0以上安装fiddler证书(模拟器)1.fiddler,最好fiddler4以上fiddler官网下载即可DownloadFiddlerWebDebuggingToolforFreebyTelerikhttps://www.telerik.com/download/fiddler2.夜神模拟器(百度下载)3.安装jdk(jdk8能够更好的支持自动化工具)JavaDownloads|Oraclehttps://www.oracle.com/java/technologies/downloads/#j

发表回复

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

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