poj 六道2-sat第五题：

题目描述：

有2n把钥匙，分成2组，给你每组的钥匙信息，并且每组的钥匙只能用一个。

有m个门，每个门有2个锁，只要打开一个锁这个门就开了。（顺序遇见m个门）

问你最多能够打开多少个门。

解题报告：

2n个钥匙，定义4n个节点，1~2n中的i表示用第i个钥匙。 2n+1~4n中的j， 表示不用j - 2n号钥匙。

那么对与给你的n组钥匙的每一组a和b。

有边<a, b + 2n> 和 <b, a + 2n>（只能选一个钥匙）

对于给你的m个门的两个锁a和b

有边<a + 2n, b> <b + 2n, a> 至少选一个。

然后枚举1~m个门，看看最后能到第几个门能够满足条件（数据比较少，不用二分也能过）

代码如下（没用二分）：

#include<iostream>
#include<cmath>
using namespace std;
#define size 6000
int n, m, v[size], cnt, ee[size][2];
struct edge{int to, next;} e[1000000];
void insert(int from, int to)
{
    e[cnt].to = to;
    e[cnt].next = v[from];//每次都插入到最前面
    v[from] = cnt++;
}
int belong[size], num[size], cntnum;
int dfn[size], low[size], index, instack[size], sta[size], top;
void tarjan(int id)
{
    dfn[id] = low[id] = ++index;
    instack[id] = 1; sta[top++] = id;
    int tmp = v[id];
    while(tmp != -1)
    {
        if (!dfn[e[tmp].to])
        {
            tarjan(e[tmp].to);
            if (low[e[tmp].to] < low[id]) low[id] = low[e[tmp].to];
        }
        else if (instack[e[tmp].to] && dfn[e[tmp].to] < low[id])
            low[id] = dfn[e[tmp].to];
        tmp = e[tmp].next;
    }
    if (dfn[id] == low[id])
    {
        do
        {
            tmp = sta[--top]; instack[tmp] = 0;
            belong[tmp] = cntnum;
            num[cntnum]++;
        }while(tmp != id);
        cntnum++;
    }
}
int main()
{
    while(scanf("%d%d", &n, &m) && (n || m))
    {
        int n2 = n + n, ans = 0, flag = true, a, b;
        memset(v, -1, sizeof(v)); cnt = 0;
        for(int i = 0; i < n ;i++)
        {
            scanf("%d%d", &a, &b);
            insert(a, b + n2); insert(b, a + n2);
        }
        for(int j = 1; j <= m; j++)
        {
            scanf("%d%d", &a, &b);
            if (flag)
            {
                insert(a + n2, b); insert(b + n2, a);
                index = top = cntnum = 0;
                memset(num, 0, sizeof(num));memset(dfn, 0, sizeof(dfn));
                for(int i = 0; i < n2; i++) if (!dfn[i]) tarjan(i);
                for(int i = 0; i < n && flag; i++)
                    flag = (belong[i] != belong[i + n2]);
                ans += flag;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}