poj 2723(二分+2-SAT)

poj 2723
二分枚举m，然后建2-SAT图即可。

#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<vector>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXM = 2100, MAXN = 1100;
struct pa
{
    int x, y;
}keis[MAXN], locs[MAXM];
int n,m;
struct twoSAT
{
    vector<int> G[MAXN*4];
    int mark[MAXN*4];
    int c;
    int S[MAXN*4];
    void init()
    {
        for (int i=0;i<4*n;i++) 
        {
            G[i].clear();
            mark[i] = false;
        }
    } 
    void addE(int x, int y, int xv, int yv)
    {
        x = x*2+xv;
        y = y*2+yv;
        G[x^1].push_back(y);
        G[y^1].push_back(x);
    }
    void built(int to)
    {
        init();
        for (int i=0;i<n;i++)
        {
            addE(keis[i].x, keis[i].y, 0, 0);
        }
        for (int i=0;i<to;i++)
        {
            addE(locs[i].x, locs[i].y, 1, 1);
        }
    }
    bool dfs(int x)
    {
        if (mark[x^1]) return false;
        if (mark[x]) return true;
        mark[x] = true;
        S[++c] = x;
        for (int i=0;i<G[x].size();i++)
        if(!dfs(G[x][i])) return false;
        return true;
    }
    bool solve()
    {
        for (int i=0;i<n*2;i++)
        if (!mark[i*2] && !mark[i*2+1])
        {
            c = 0;
            if (!dfs(i*2))
            {
                while (c>0) mark[S[c--]] = false;
                if (!dfs(i*2+1)) return false;
            }
        }
        return true;
    }
}ts;
int main()  
{  
    while (scanf("%d%d", &n,&m)==2&&(n||m))
    {
        for (int i=0;i<n;i++)
        {
            scanf("%d%d", &keis[i].x, &keis[i].y);
        }
        for (int i=0;i<m;i++)
        {
            scanf("%d%d", &locs[i].x, &locs[i].y);
        }
        int l = 0,  r = m, mid;
        while (l<r)
        {
            mid = (l+r)/2+1;
            ts.built(mid);
            bool ans = ts.solve();
            if (ans) l = mid; else r = mid-1;
        }
        printf("%d\n", l);
    }
    return 0;  
}