首页 > 代码库 > Gym 100851K
Gym 100851K
Problem King‘s Inspection
题目大意
给一张n个点m条边的无向图,问是否存在一条欧拉回路。
n<=10^5, 0<=m<=n+20。
解题分析
注意到数据范围m<=n+20,可以想象若存在一条欧拉回路,那么图的形状必定是一条长链再加上20条边。
将连续的一段入度和出度均为0的点缩成一个点,之后暴力跑欧拉回路就行了。
参考程序
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17 18 #define V 1000008 19 #define E 2000008 20 #define LL long long 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1 23 #define clr(x,v) memset(x,v,sizeof(x)); 24 #define bitcnt(x) __builtin_popcount(x) 25 #define rep(x,y,z) for (int x=y;x<=z;x++) 26 #define repd(x,y,z) for (int x=y;x>=z;x--) 27 const int mo = 1000000007; 28 const int inf = 0x3f3f3f3f; 29 const int INF = 2000000000; 30 /**************************************************************************/ 31 32 int lt[V],sum,indeg[V],outdeg[V],vis[V],cnt,nt[V],LT[V],SUM,fa[V],succ[V]; 33 34 struct line{ 35 int u,v,nt,flag; 36 }eg[E],EG[E]; 37 38 void add(int u,int v){ 39 eg[++sum]=(line){u,v,lt[u],1}; 40 lt[u]=sum; 41 indeg[v]++; outdeg[u]++; 42 } 43 void ADD(int u,int v){ 44 EG[++SUM]=(line){u,v,LT[u],1}; 45 LT[u]=SUM; 46 } 47 int n,m; 48 bool check(int u){ 49 return indeg[u]==1 && outdeg[u]==1; 50 } 51 void dfs(int u){ 52 vis[u]=1; cnt++; 53 for (int i=lt[u];i;i=eg[i].nt){ 54 int v=eg[i].v; 55 if (vis[v]) continue; 56 if (check(v) && check(u) && eg[lt[v]].v!=u){ 57 nt[u]=v; fa[v]=u; 58 eg[i].flag=0; 59 } 60 dfs(v); 61 } 62 } 63 64 bool find(int u,int num){ 65 if (u==1 && num==cnt) return 1; 66 if (u==1 && num!=0) return 0; 67 for (int i=LT[u];i;i=EG[i].nt){ 68 int v=EG[i].v; 69 if (fa[v]) continue; 70 fa[v]=u; succ[u]=v; 71 if (find(v,num+1)) return 1; 72 fa[v]=0; 73 } 74 return 0; 75 } 76 77 int main(){ 78 freopen("king.in","r",stdin); 79 freopen("king.out","w",stdout); 80 scanf("%d%d",&n,&m); 81 rep(i,1,m){ 82 int u,v; 83 scanf("%d%d",&u,&v); 84 add(u,v); 85 } 86 add(1,1); 87 clr(vis,0); cnt=0; 88 dfs(1); 89 if (cnt!=n) { printf("There is no route, Karl!\n"); return 0; } 90 cnt=n; 91 clr(vis,0); 92 rep(i,1,sum) 93 if (eg[i].flag) ADD(eg[i].u,eg[i].v); 94 else 95 { 96 int l=eg[i].u,r=eg[i].v; 97 if (vis[l]||vis[r]) continue; 98 while (fa[l]) l=fa[l]; 99 while (nt[r]) r=nt[r];100 r=eg[lt[r]].v;101 ADD(l,r);102 int x=l;103 while (nt[x])104 {105 x=nt[x];106 cnt--;107 vis[x]=1;108 }109 }110 clr(fa,0);111 if (!find(1,0)) { printf("There is no route, Karl!\n"); return 0; }112 int u=1;113 while (1){114 printf("%d ",u);115 int uu=nt[u];116 while (uu)117 {118 printf("%d ",uu);119 uu=nt[uu];120 }121 u=succ[u];122 if (u==1) break;123 }124 printf("1\n");125 }
Gym 100851K
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。