首页 > 其他分享 >P7771 【模板】欧拉路径

P7771 【模板】欧拉路径

时间:2024-04-06 16:33:06浏览次数:28  
标签:Node head P7771 int cnt dfs Next 模板 欧拉

原题链接

题解

链式前向星版本的欧拉回路dfs

void dfs(int u){
    for (int i=head[u];i>0;i=head[u]){
        head[u]=Next[i];   //走过的路直接跳过
        dfs(to[i]);
    }
    que[l++]=u;
}

接下来的难点是如何字典序搜索。我们在dfs的时候直接让走字典序最小的边即可;而由于链式前向星是从后往前枚举的,我们需要对所有的边进行排序。

bool cmp(Node a,Node b){
    if (a.u!=b.u) return a.u<b.u;
    return a.v>b.v;  //保证每次枚举都是字典序最小的边
}

code

 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=2e5+5;
int head[N],Next[M],to[M],in[N],out[N];
struct Node{
    int u,v;
};
Node a[M];
bool cmp(Node a,Node b){
    if (a.u!=b.u) return a.u<b.u;
    return a.v>b.v;
}
int cnt=1,l=0;
int que[M];
void build(int i){
    Next[cnt]=head[a[i].u];
    to[cnt]=a[i].v;
    head[a[i].u]=cnt++;
}
void dfs(int u){
    for (int i=head[u];i>0;i=head[u]){
        head[u]=Next[i];
//        cout<<u<<" "<<to[i]<<endl;
        dfs(to[i]);
    }
    que[l++]=u;
}
int main(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v;
        in[a[i].v]++;
        out[a[i].u]++;
    }
    int n1=0,n2=0,start=1,end=n;
    for (int i=1;i<=n;i++){
        if (in[i]-out[i]==1){
            n1++;
            end=i;
            continue;
        }
        if (out[i]-in[i]==1){
            n2++;
            start=i;
            continue;
        }
        if (in[i]!=out[i]){
            cout<<"No\n";
            return 0;
        }
    }
    if ((n1==0 && n2==0) || (n1==1 && n2==1)){
        sort(a+1,a+m+1,cmp);
//        for (int i=1;i<=m;i++) cout<<a[i].u<<" "<<a[i].v<<endl;
        for (int i=1;i<=m;i++) build(i);
        dfs(start);
        while (l){
            if (l) cout<<que[--l]<<" ";
            else cout<<que[--l];
        }
    }
    else cout<<"No\n";
    return 0;
}

 

标签:Node,head,P7771,int,cnt,dfs,Next,模板,欧拉
From: https://www.cnblogs.com/purple123/p/18117539

相关文章

  • 倍增(LCA与ST表)附详细讲解博客路劲以及洛谷模板题
    前置知识--倍增倍增算法,顾名思义,就是不断地翻倍。虽然是一种基础算法,但它能够使得线性的处理转化为对数级的处理,大大地优化时间复杂度,在很多算法中都有应用,其中最常见的就是ST表以及LCA(树上最近公共祖先)了。学习博客:算法学习笔记(12):ST表-知乎(zhihu.com)for(intx=......
  • 线段树模板
    #include<iostream>#include<map>#include<algorithm>#include<math.h>usingnamespacestd;/*3372*/typedeflonglongll;constintN=1e5+10;lla[N]={0};lltree[N<<2]={0};lltag[N<<2]={0};llls(......
  • P1439 【模板】最长公共子序列
    题面:回顾下最长公共子序列:if(a[i]!=b[j])dp[i][j]=max(dp[i-1][j],dp[i][j-1]);elsedp[i][j]=dp[i-1][j-1]+1;复杂度为O(n^2)但是这题不行,数据卡到了1e5,所以应该再次观察:注意到是两个全排列,那么利用map,把第一个序列当作基准列,做等效替换:把原来的值替换成1,2,3.........
  • 最长上升子序列LIS模板
    参考链接:https://blog.csdn.net/lxt_Lucia/article/details/81206439#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<string.h>#include<iomanip>......
  • C111【模板】莫队算法 P2709 小B的询问
    视频链接:C111【模板】莫队算法P2709小B的询问_哔哩哔哩_bilibili   LuoguP2709小B的询问//普通莫队O(n*sqrt(n))#include<iostream>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;constintN=50005;intn,m,k,B,a[N];......
  • 帝国CMS模板源码整站安装说明
    安装步骤第一步:先把得到的文件解压缩,把文件通过FTP传到空间里。(请不要把类似ecms014.cncobo.com这个文件夹传到FTP,请传这个大文件夹下面的所有文件夹和文件到空间根目录,请不要上传到2级目录,除非你自己会改模板CSS和JS调用相对地址!)第二步:浏览器键入你的域名或者IP/e/install/inde......
  • django渲染模板与vue的语法冲突解决Flask框架默认WSGI:Werkzeug
    django渲染模板与vue的语法冲突解决Flask框架默认WSGI:Werkzeug Python来说,它有很多web框架,常见的有jango、Flask、Tornado、sanic等,比如Odoo、Superset都基于Flask框架进行开发的开源平台,具有强大的功能。在Linux下,默认使用的WSGIServer一般为Gunicorn,它是一个比较出名的We......
  • P5960 【模板】差分约束
    原题链接题解我一直苦苦思考为什么要建边,现在我明白了,如果令\(x_i\)代表离源点的最短路径长度的话,建边之后,\(x_i-x_j<=y_k\)一定成立只有当出现负环的时候说明条件出现了矛盾太神了code#include<bits/stdc++.h>usingnamespacestd;queue<int>q;intin_q[5005]={0};......
  • nodejs中使用Nunjucks 模板引擎
    要在Koa2中使用Nunjucks模板引擎,你需要进行一些额外的设置。以下是一个示例代码,演示了如何在Koa2中集成Nunjucks:首先,确保已经安装了Koa和Nunjucks:npminstallkoanunjucks然后,在项目中创建一个名为app.js的文件,并添加以下代码:constKoa=require('koa');con......
  • 【Java】PDF模板生成PDF文档
    一、需求背景客户要求一份文书,文书内容有一些表单项,例如:1、基本的是和否(单选框或复选框)2、备注内容(纯文本信息)3、单位,机构组织,人员,字典项(下拉选择)4、用户数字签名(图片信息)文书的模板是固定不变的,只需要把上述信息写入模板中生成即可这个模板不是动态的,动态模板是表单数据......