get luffy out(2-sat).cpp

杭电acm解题报告2001---2099.

//对于钥匙a，记A为选择钥匙a为真，记﹁A为选择钥匙a为假
//对于每对钥匙a, b，若A则﹁B，若B则﹁A 
//对于每扇门，想要打开门上的两个锁a, b，若﹁A则B，若﹁B则A
//2-SAT判断是否合法
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 1100*2*2
#define MMAX 2200

int n,m;
vector< vector<int> > path;
int doors[MMAX][2];

int scc, step;
int order[NMAX], order_pos, id[NMAX];
int order2[NMAX], order2_pos;
int vis[NMAX];

void dfs(int pos)
{
    int i,next,l,pre;
	
    vis[pos] = step ++;
    order[ order_pos ++ ] = pos;
    order2[ order2_pos ++ ] = pos;
    l = path[pos].size();
    for (i=0;i<l;i++) {
        next = path[pos][i];
        if (vis[next] == 0) {
            dfs(next);
        }
        else if (id[next] == 0) {//have a circle and belong to nothing
            while (vis[ order2[order2_pos -1] ] > vis[next]) {//back to begin of circle
                order2_pos --;
            }
        }
    }//for i
    if (order2[order2_pos -1] == pos) {//if pos back to begin of scc
        order2_pos --;
    }
    else {
        return ;
    }
    do {//record scc
        pre = order[order_pos -1];
        id[pre] = scc;
        order_pos --;
    } while(pre != pos);
    scc ++;
}

int Gabow()
{
    int i;
    //dfs in original graph
    memset(id, 0, sizeof(id));
    memset(vis, 0, sizeof(vis));
    scc = step = 1;
    order_pos = order2_pos = 0;
    for (i=0; i<4*n ;i++) {
        if (vis[i] == 0) {
            dfs(i);
        }
    }
    //statist
    scc --;
	for (i=0;i<4*n;i+=2) {
		if (id[i] == id[i+1]) {
			return false;
		}
	}
	return true;
}

int enum_answer()
{
	int i, mmax, x, y;
	bool flag = true;
	mmax = 0;
	for (i=1;i<=m;i++) {
		scanf("%d %d",&x, &y);
		if ( flag ) {
			path[ 2*x +1 ].push_back(2*y);
			path[ 2*y +1 ].push_back(2*x);
			flag = Gabow();
			mmax = flag ? i : mmax;
		}
	}
	return mmax;
}

bool check(int mid)
{
	int i, x, y;
	for (i=1;i<=mid;i++) {
		x = doors[i][0];
		y = doors[i][1];
		path[ 2*x +1 ].push_back(2*y);
		path[ 2*y +1 ].push_back(2*x);
	}
	return Gabow();
}

int binary_answer()
{
	int i, mmax;
	vector< vector<int> > temp_path;

	for (i=1;i<=m;i++) {
		scanf("%d %d",&doors[i][0], &doors[i][1]);
	}

	int left = 0, right = m, mid;
	temp_path = path;
	while (right > left) {
		mid = (left + right) / 2;
		if ( check(mid) ) {
			left = mid;
		}
		else {
			right = mid -1;
		}
		path = temp_path;
	}
	return left;
}

int main()
{
	int i,x,y;
	while (scanf("%d %d",&n,&m)==2) {
		if (n == 0 && m ==0) {
			break ;
		}
		path.resize(4*n+10);
		for (i=0;i<=4*n;i++) {
			path[i].clear();
		}
		for (i=0;i<n;i++) {
			scanf("%d %d",&x,&y);
			path[2*x].push_back(2*y +1);
			path[2*y].push_back(2*x +1);
		}
		printf("%d\n", enum_answer());
		//printf("%d\n", binary_answer());//TLE, may be STL's vector is inefficiency
	}
}