牛客CSP-S提高组赛前集训营1 C 小w的魔术扑克

$Hyperlink$

https://ac.nowcoder.com/acm/contest/1100/C

$Description$

给定$n$张双面牌，每张牌的每一面分别写着$a_i,b_i$，给定$m$组询问，问你是否能用这些牌打出$l_i,r_i$的顺子

数据范围：

$Solution$

匈牙利+牌相同的特判可以拿到40分。。。代码详见总结

考虑将原题图论化，如果我们让$a_i->b_i$，那么这就构成了一张图，一个顺子合法当且仅当这张图联通且带环

所以我们并查集预处理，处理出对于每个数$x$，他顺子的起点的最小值$l[x]$，就可以$O(1)$判断了

总的时间复杂度：$O(nlogn)$

$Code$

#include<cctype>
#include<cstdio>
#include<algorithm>
#define N 100010
#define LL long long
using namespace std;int f[N],mx,n,q,x,y,belong[N],maxn,l[N];
bool h[N];
inline int find(register int x){return x==f[x]?x:f[x]=find(f[x]);}
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{mx=read();n=read();for(register int i=1;i<=mx;i++) f[i]=i,belong[i]=i;for(register int i=1;i<=n;i++){x=find(read());y=find(read());if(x>y) x^=y,y=x^y,x^=y;if(x==y) h[x]=true;else h[x]|=h[y],f[y]=x,belong[x]=max(belong[x],belong[y]);}for(register int i=1;i<=mx;i++){int x=find(i);if(belong[x]==i&&!h[x]) maxn=max(maxn,x);l[i]=maxn;}q=read();while(q--){x=read();y=read();puts(x>l[y]?"Yes":"No");}
}