首页 > 代码库 > Gym 100851K

Gym 100851K

2024-08-11 10:02:45   220人阅读

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 }
View Code

 

Gym 100851K


联系
我们