【AtCoder Grand Contest 017 E】Jigsaw | Mrsrz's blog

欧拉路径，并查集。

题目大意：

给定 $n$ 个物体，每个物体跨过 $3$ 个横坐标，中间高度为 $h$，左右两边分别会有一部分突出（可能悬空，有高度）。

问是否存在一种摆放方案，使得每个物体中间着地，两边不悬空（要么着地要么下面有别的物体垫着）。

题解：

我们可以把每个问题左右两边看成插头。

然后对于 $A,B,C,D$，若 $C=0$，则左边的插头为 $A$，否则为 $-C$。同理若 $D=0$，则右边的插头为 $-B$，否则为 $D$。

可以发现，插头相同的可以拼起来。

然后我们把 $-2h\sim 2h$ 看成点，一个物体就代表左边的点向右边的点连出一条有向边。我们记录一个点的入度和出度即可。

然后为了满足图中的条件，这张图应当由若干条欧拉路径组成，且起点的插头大于等于 $0$，终点的插头小于等于 $0$。所以对于 $-2h\sim 0$ 的点，其出度应小于等于入度；对于 $0\sim 2h$ 的点，其入度应小于等于出度。

然后，一个弱连通块里必须存在一个入度和出度不相等的点，否则会形成自己连自己的情况。

用并查集判断即可。

Code：

#include<cstdio>
const int N=2e5+7;
int in[N],out[N],fa[N],n,h;
bool vis[N];
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
int main(){
    scanf("%d%d",&n,&h);
    for(int i=0;i<=2*h;++i)fa[i]=i;
    for(int i=1;i<=n;++i){
        int A,B,C,D;
        scanf("%d%d%d%d",&A,&B,&C,&D);
        int iL=C==0?A:-C,iR=D==0?-B:D;
        ++in[iL+=h],++out[iR+=h];
        if(find(iL)!=find(iR))fa[fa[iL]]=fa[iR];
    }
    bool ok=1;
    for(int i=0;i<=2*h&&ok;++i)
    if(in[i]||out[i]){
        if(i<=h&&in[i]>out[i])ok=0;
        if(i>h&&in[i]<out[i])ok=0;
        if(in[i]!=out[i])vis[find(i)]=1;
    }
    for(int i=0;i<=2*h&&ok;++i)
    if(in[i]||out[i])if(!vis[find(i)])ok=0;
    puts(ok?"YES":"NO");
    return 0;
}