钥匙编号0123456...2n-1），每对钥匙只能用一把,要求尽可能开门多（按顺序，前max个）。
关键是题意的分析与转化，只能选一？必然2-sat，每给一对门上的锁对应钥匙的编号，说：必需要这
俩把钥匙的一把（至少），即：a^b，所以，建图了可以，总结通法：对应的数据编号：0123..，每个数代表原来的一个“状态”/“命题”/“数据”，使之01为一对（只取一个），23一对，...依次，建图
此题要求最值，二分即可。
注意点（WA之因）：1.编号后全图全按编号走啊！原来数据基本无用，只是有时候输出时之用，或建立
数据双向关系！2.对于每次二分，对应数要重新建图，注意初始化！
ps:一晚没成功，结果早上起来2分钟，AC！上午效率就是高！切记不可熬夜！身体健康第一位！
#include<iostream> //36MS
#include<cstring>
#include<cstdio>
#include<stack>
#include<vector>
using namespace std;
const int MAX=3000;
vector<int>keys(MAX);int n,m;int times=0;
int belong[MAX];
int low[MAX];int dfn[MAX];int visited[MAX];int isinstack[MAX];stack<int>s;
int scc[MAX];int numblock=0;
struct request //条件
{
int a,b;
};
request requests[MAX];
vector<vector<int> >edges(MAX); //图
void clear()
{
times=numblock=0;
for(int i=0;i<2*n;i++)
{
visited[i]=dfn[i]=low[i]=isinstack[i];
scc[i]=-1;
edges[i].clear();
}
}
void tarjan(int u) //dfs
{
dfn[u]=low[u]=++times;
isinstack[u]=1;
s.push(u); int len=edges[u].size();
for(int i=0;i<len;i++)
{
int v=edges[u][i];
if(visited[v]==0)
{
visited[v]=1;
tarjan(v);
if(low[u]>low[v])low[u]=low[v];
}
else if(isinstack[v]&&dfn[v]<low[u])
low[u]=dfn[v];
}
if(low[u]==dfn[u])
{
numblock++;int cur;
do
{
cur=s.top();s.pop();
isinstack[cur]=0;
scc[cur]=numblock;
}while(cur!=u);
}
}
bool check(int maxnum) //检查
{
clear();
for(int i=0;i<maxnum;i++) //这里的数据的转化
{
if(requests[i].a==requests[i].b)
{
edges[belong[requests[i].a]^1].push_back(belong[requests[i].b]);
}
else
{
edges[belong[requests[i].a]^1].push_back(belong[requests[i].b]);
edges[belong[requests[i].b]^1].push_back(belong[requests[i].a]);
}
}
for(int i=0;i<2*n;i++)
if(visited[i]==0)
{
visited[i]=1;
tarjan(i);
}
for(int i=0;i<2*n;i+=2)
if(scc[i]==scc[i+1]) //因为这里跪了半天！注意编号！图顶点用的都是编号！
return 0;
return 1;
}
void readin()
{
for(int i=0;i<2*n;i++)
{
scanf("%d",&keys[i]);
belong[keys[i]]=i;
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&requests[i].a,&requests[i].b);
}
}
int main()
{
while(~scanf("%d%d",&n,&m)&&(n||m))
{
readin();
int left=0,right=m,mid;
int count=-1;
while(right>left) //二分之
{
mid=(left+right)/2;
if(mid==count&&mid==left) //注意出口！
{
if(check(left+1))left++;
break;
}
if(check(mid))
left=mid;
else right=mid;
count=mid;
}
printf("%d
",left);
}
}