一道很基础的2-sat，题目链接戳这里。
大意是，你有n对钥匙，每对钥匙中只能选一个。你要开m个门，每个门可以用两把给定钥匙中的任意一把打开，问你最多能开到第几道门。
为了方便处理，我们先做个映射，把第i对钥匙的编号转换为i*2和i*2+1。然后将门当做限制连边，每读入一个就连一条边，判定是否可行，直到不可行为止。
poj2723
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
using namespace std;
int mp[10000];
int tot;
int had[5050],nxt[5000],point[5005];
int t;
int dfn[20000],low[20000];
int blng[20000];
inline void add(int x,int y)
{
tot++;
point[tot]=y;
nxt[tot]=had[x];
had[x]=tot;
}
stack<int> ss;
bool vis[20000];
void tarjan(int x)
{
t++;
dfn[x]=low[x]=t;
vis[x]=1;
ss.push(x);
for(int i=had[x];i!=-1;i=nxt[i])
{
int to=point[i];
if(!dfn[to])
{
tarjan(to);
low[x]=min(low[x],low[to]);
}
else if(vis[to])low[x]=min(low[x],dfn[to]);
}
if(low[x]==dfn[x])
{
int y=ss.top();
while(!ss.empty())
{
y=ss.top();
ss.pop();
blng[y]=x;
vis[y]=0;
if(y==x)break;
}
}
}
int main()
{
int n,m;
while(cin>>n>>m&&n)
{
tot=0;
memset(had,-1,sizeof(had));
memset(nxt,-1,sizeof(nxt));
memset(point,-1,sizeof(point));
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
mp[a]=2*i;
mp[b]=2*i+1;
}
bool f=0;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
if(f)continue;
add(mp[a],mp[b]^1);
add(mp[b],mp[a]^1);
t=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis));
memset(blng,0,sizeof(blng));
for(int j=0;j<2*n;j++)
if(!dfn[j])tarjan(j);
for(int j=0;j<2*n;j+=2)
if(blng[j]==blng[j+1])
{
cout<<i-1<<endl;
f=1;
break;
}
}
if(f==0)cout<<m<<endl;
}
return 0;
}