Gym 100851K

时间:2022-02-09 03:37:16

Problem King's Inspection

题目大意

  给一张n个点m条边的无向图,问是否存在一条欧拉回路。

  n<=10^5, 0<=m<=n+20。

解题分析

  注意到数据范围m<=n+20,可以想象若存在一条欧拉回路,那么图的形状必定是一条长链再加上20条边。

  将连续的一段入度和出度均为0的点缩成一个点,之后暴力跑欧拉回路就行了。

参考程序

 #include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std; #define V 1000008
#define E 2000008
#define LL long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define clr(x,v) memset(x,v,sizeof(x));
#define bitcnt(x) __builtin_popcount(x)
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define repd(x,y,z) for (int x=y;x>=z;x--)
const int mo = ;
const int inf = 0x3f3f3f3f;
const int INF = ;
/**************************************************************************/ int lt[V],sum,indeg[V],outdeg[V],vis[V],cnt,nt[V],LT[V],SUM,fa[V],succ[V]; struct line{
int u,v,nt,flag;
}eg[E],EG[E]; void add(int u,int v){
eg[++sum]=(line){u,v,lt[u],};
lt[u]=sum;
indeg[v]++; outdeg[u]++;
}
void ADD(int u,int v){
EG[++SUM]=(line){u,v,LT[u],};
LT[u]=SUM;
}
int n,m;
bool check(int u){
return indeg[u]== && outdeg[u]==;
}
void dfs(int u){
vis[u]=; cnt++;
for (int i=lt[u];i;i=eg[i].nt){
int v=eg[i].v;
if (vis[v]) continue;
if (check(v) && check(u) && eg[lt[v]].v!=u){
nt[u]=v; fa[v]=u;
eg[i].flag=;
}
dfs(v);
}
} bool find(int u,int num){
if (u== && num==cnt) return ;
if (u== && num!=) return ;
for (int i=LT[u];i;i=EG[i].nt){
int v=EG[i].v;
if (fa[v]) continue;
fa[v]=u; succ[u]=v;
if (find(v,num+)) return ;
fa[v]=;
}
return ;
} int main(){
freopen("king.in","r",stdin);
freopen("king.out","w",stdout);
scanf("%d%d",&n,&m);
rep(i,,m){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
add(,);
clr(vis,); cnt=;
dfs();
if (cnt!=n) { printf("There is no route, Karl!\n"); return ; }
cnt=n;
clr(vis,);
rep(i,,sum)
if (eg[i].flag) ADD(eg[i].u,eg[i].v);
else
{
int l=eg[i].u,r=eg[i].v;
if (vis[l]||vis[r]) continue;
while (fa[l]) l=fa[l];
while (nt[r]) r=nt[r];
r=eg[lt[r]].v;
ADD(l,r);
int x=l;
while (nt[x])
{
x=nt[x];
cnt--;
vis[x]=;
}
}
clr(fa,);
if (!find(,)) { printf("There is no route, Karl!\n"); return ; }
int u=;
while (){
printf("%d ",u);
int uu=nt[u];
while (uu)
{
printf("%d ",uu);
uu=nt[uu];
}
u=succ[u];
if (u==) break;
}
printf("1\n");
}

Gym 100851K的更多相关文章

  1. ACM&colon; Gym 101047M Removing coins in Kem Kadr&&num;227&semi;n - 暴力

     Gym 101047M Removing coins in Kem Kadrãn Time Limit:2000MS     Memory Limit:65536KB     64bit IO Fo ...

  2. ACM&colon; Gym 101047K Training with Phuket&&num;39&semi;s larvae - 思维题

     Gym 101047K Training with Phuket's larvae Time Limit:2000MS     Memory Limit:65536KB     64bit IO F ...

  3. ACM&colon; Gym 101047E Escape from Ayutthaya - BFS

    Gym 101047E Escape from Ayutthaya Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%I6 ...

  4. ACM&colon; Gym 101047B Renzo and the palindromic decoration - 手速题

     Gym 101047B  Renzo and the palindromic decoration Time Limit:2000MS     Memory Limit:65536KB     64 ...

  5. Gym 101102J---Divisible Numbers&lpar;反推技巧题&rpar;

    题目链接 http://codeforces.com/gym/101102/problem/J Description standard input/output You are given an a ...

  6. Gym 100917J---Judgement&lpar;01背包&plus;bitset&rpar;

    题目链接 http://codeforces.com/gym/100917/problem/J Description standard input/outputStatements The jury ...

  7. Gym 100917J---dir -C(RMQ--ST)

    题目链接 http://codeforces.com/gym/100917/problem/D problem description Famous Berland coder and IT mana ...

  8. Gym 101102D---Rectangles&lpar;单调栈&rpar;

    题目链接 http://codeforces.com/gym/101102/problem/D problem  description Given an R×C grid with each cel ...

  9. Gym 101102C---Bored Judge(区间最大值)

    题目链接 http://codeforces.com/gym/101102/problem/C problem description Judge Bahosain was bored at ACM ...

随机推荐

  1. Hacker Rank&colon; Two Strings - thinking in C&num; 15&plus; ways

    March 18, 2016 Problem statement: https://www.hackerrank.com/challenges/two-strings/submissions/code ...

  2. 线性结构CT 02-线性结构1 一元多项式的乘法与加法运算

    设计函数分别求两个一元多项式的乘积与和. 输入格式: 输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数).数字间以空格分隔. ...

  3. [terry笔记]物化视图 materialized view基础学习

    一.物化视图定义摘录:     物化视图是包括一个查询结果的数据库对像(由系统实现定期刷新数据),物化视图不是在使用时才读取,而是预先计算并保存表连接或聚集等耗时较多的操作结果,这样在查询时大大提高了 ...

  4. xshell使用命令总结

    这个工具主要是链接linux 并且可以从linux上面下载文件到本地 还有上传本地文件到linux上面 下载首先需要压缩打包命令为: tar -cf am_mailer.tar * sz am_mai ...

  5. Linux常用命令汇总及使用方法(二)之文本编辑器VI

    VI可能是在Linux中使用比较频繁的文本编辑器,如果不能熟练使用VI,在一定程度上会影响工作效率,所以在这里记录一下VI的常用命令及操作方式 在[root@test ~]# vi carrie.tx ...

  6. hdu 1233 还是畅通project(kruskal求最小生成树)

    还是畅通project Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Tota ...

  7. 保存xml报错 &&num;39&semi;UTF&lowbar;8&&num;39&semi; is not a supported encoding name

    ArgumentException: 'UTF_8' is not a supported encoding name. For information on defining a custom en ...

  8. &period;NetCore生产环境下构建Consul(单个DC数据中心)的服务器健康检查

    下载最新的consul程序 consul 启动方式有两种 server 和client 默认是client 如果你不需要记录数据可以用 consul agent -dev 来启动 consul age ...

  9. linux下pgAdmin4安装

    首先到pgAdmin4官方网站下载安装包:https://www.pgadmin.org/download/ 我下载的是3.0; 到文件所在目录执行安装命令: sudo pip install ./p ...

  10. C&plus;&plus;进阶3&period;字节对齐 联合

    C++进阶3.字节对齐 联合 20131011 多益和金山笔试 知识漏洞 20131011 前言: 今天下午是多益网络的笔试,整体感觉还好,但是找到很多的知识漏洞.一直笔试到6:00,然后紧张的从会生 ...