题意分析

题目中给定 $N$ 对钥匙，每对钥匙你只能选择其中一把，而每扇门上有两个锁，对应两个钥匙编号。目标是选择钥匙使得从第一扇门开始能顺序打开尽可能多的门。

解题思路

Ratish 需要依顺序打开尽可能多的门，打开一扇门的条件是，从选定的钥匙中至少包含门上两个锁中的一个。由于门是顺序排列的，因此我们需要找到一个最大的门数 $m$，使得前 $m$ 扇门对应的约束都可以同时满足。

对于每扇门，可以构造如下逻辑约束：

表示从门上两把对应的钥匙中至少需要选中一个。结合“每对钥匙只能选一把”的限制，我们可以将问题建模为一个典型的 $2$-SAT 问题。

1. 构造 $2$-SAT 模型

• 变量构造：
  每对钥匙对应一个布尔变量，例如令第 $i$ 对钥匙中选中某一把表示为一个变量。可以把每种选择看作一个字面值，并用编号转换为两个节点表示变量及其否定。
• 约束转换：
  对于每扇门给定的钥匙编号 $a$ 和 $b$，其 “或” 约束 $p \vee q$ 可以转换为两个蕴涵：$$\lnot p \to q \quad \text{和} \quad \lnot q \to p.$$ 将所有门的约束均建立相应的有向边，同时加上每对钥匙的互斥限制（只能选择一把），构成隐含图。

2. 利用 Tarjan 算法判定 $2$-SAT 的可满足性

在构造隐含图后，关键在于判断这个 $2$-SAT 系统是否有解。这里就需要用到 Tarjan 算法，它能够在 $O(V+E)$ 的时间复杂度内找到有向图中的所有强连通分量，判断是否存在某对变量和其否定在同一分量内；只有当不存在这种情形时，当前门数 $m$ 才是可行的。 Tarjan 算法的主要思想为：

• 为每个节点分配 DFS（深度优先搜索） 序号 $dfn$，并维护每个节点的最低能到达节点的序号 $low$。
• 在 DFS 过程中，将节点压入栈中。若某节点的 $low$ 值等于它的 $dfn$ 值，则从栈中弹出构成一个强连通分量。
• 若对于任一变量 $p$，其对应的节点和其否定节点 $\lnot p$ 出现在同一强连通分量中，则说明该 $2$-SAT 系统无解。

3. 二分搜索

由于门是按照 Ratish 见到的顺序排列的，我们可以利用二分搜索确定最大的 $m$ 值。对于一个给定的 $m$，我们构造前 $m$ 扇门的约束隐含图，利用 Tarjan 算法检测其中的 $2$-SAT 系统是否可满足。如果满足，则说明可以打开 $m$ 扇门，可以尝试更大的 $m$；否则必须减小 $m$。

最终，二分搜索获得的最大 $m$ 就是 Ratish 最多可以顺序打开的门数。

结合上述各部分，整个求解过程就是：

1. 根据每对钥匙和每扇门构造 $2$-SAT 隐含图（建立蕴涵边）；
2. 利用 Tarjan 算法检测隐含图中强连通分量的关系，判断 $2$-SAT 系统的可解性；
3. 采用二分搜索确定能够满足约束的最大门数。

本题代码

#include<cstdio>
#include<iostream>
using namespace std;
const int mm=4444;
const int mn=2222;
int ver[mm],next[mm];
int head[mn],dfn[mn],low[mn],q[mn],id[mn],x[mn],a[mn],b[mn];
int i,n,m,idx,cnt,top,edge,l,r,ans;
void add(int u,int v)
{
    ver[edge]=v,next[edge]=head[u],head[u]=edge++;
}
void dfs(int u)
{
    dfn[u]=low[u]=++idx;
    q[top++]=u;
    for(int i=head[u],v;i>=0;i=next[i])
        if(!dfn[v=ver[i]])
            dfs(v),low[u]=min(low[u],low[v]);
        else if(!id[v])low[u]=min(low[u],dfn[v]);
    if(low[u]==dfn[u])
    {
        id[u]=++cnt;
        while(q[--top]!=u)id[q[top]]=cnt;
    }
}
void Tarjan()
{
    for(idx=cnt=top=i=0;i<n+n;++i)dfn[i]=id[i]=0;
    for(i=0;i<n+n;++i)
        if(!dfn[i])dfs(i);
}
bool ok()
{
    for(edge=i=0;i<n+n;++i)head[i]=-1;
    for(i=0;i<m;++i)
    {
        add(x[a[i]],x[b[i]]^1);
        add(x[b[i]],x[a[i]]^1);
    }
    Tarjan();
    for(i=0;i<n+n;i+=2)
        if(id[i]==id[i^1])return 0;
    return 1;
}
int main()
{
    while(scanf("%d%d",&n,&m),n+m)
    {
        for(i=0;i<n;++i)
        {
            scanf("%d%d",&l,&r);
            x[l]=i<<1|1,x[r]=i<<1;
        }
        for(i=0;i<m;++i)
            scanf("%d%d",&a[i],&b[i]);
        ans=l=0,r=m;
        while(l<=r)
        {
            m=(l+r)>>1;
            if(ok())ans=m,l=m+1;
            else r=m-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}