2sat 问题2.cpp

对于给定的2-CNF

#include <math.h>
#include <fstream.h>

int n;//实际顶点数
int grt;//转置标志
int **g;//邻接矩阵
int *c,*a1,*a2;//顶点颜色表，顶点前驱表，完成时刻顺序表，辅助表
int color,m;//颜色，完成时刻排序表指针
int *a;
int sum;
ifstream infile("input.txt");
ofstream outfile("output.txt");

void swap(int &x,int &y)
{
	int t;
    t=x;
    x=y;
    y=t;
}

int partition(int a[],int p,int r)
{
	int i=p,j=r+1,k=a[p];
    while(true)
	{
		while (a[++i]>k);
        while (a[--j]<k);
        if(i>=j) break;
        swap(a[i],a[j]);
	}
    a[p]=a[j];
    a[j]=k;
    return j;
}

void quicksort(int a[],int p,int r)
{
 if(p<r)
 {
	 int q=partition(a,p,r);
     quicksort(a,p,q-1);
     quicksort(a,q+1,r);
 }
}

void dfsvisit(int u)//搜索以u为根的深度优先树
{
	c[u]=-color;//灰色
	for(int v=1;v<=n;v++)
		if(g[u][v]>0)
			if(c[v]==0)
				dfsvisit(v);
	c[u]=color;//黑色
	if(grt==1) a[++sum]=u;
	else
	{
	 a1[m]=u;
	 m--;
	}
}

void dfs()
{
	int u;
	for(int i=1;i<=n;i++) a2[i]=a1[i];
	for(i=1;i<=n;i++) c[i]=0;
	color=0;
	m=n;
	for(u=1;u<=n;u++)
	{
		if(c[a2[u]]==0)
		{
			color++;
			if(grt==1) sum=0;
			dfsvisit(a2[u]);
		    if(grt==1)
			{
				quicksort(a,1,sum);
			    for(int i=1;i<sum;i++)
				{
					if((a[i]-a[i+1]==1)&&(a[i]%2==0)) 
					{
						cout<<"No";
						outfile<<"No";
					    return;
					}
				}
			}
		}
	}
	if(grt==1) {cout<<"Yes";outfile<<"Yes";}
	 
}

void input()
{
	int k,m,u,v;
	int i,j;
	infile>>k>>m;
	n=2*k;
	g=new int*[n+1];
	for(i=1;i<=n;i++) g[i]=new int[n+1];
	c=new int[n+1];
	a1=new int[n+1];
	a2=new int[n+1];
	a=new int[n+1];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			g[i][j]=0;
	for(i=1;i<=n;i++) a1[i]=i;
    for(i=1;i<=m;i++)
	{
		infile>>u>>v;
		if(u>0&&v>0) {g[2*u][2*v-1]=1;g[2*v][2*u-1]=1;}
		if(u>0&&v<0) {g[2*u][2*abs(v)]=1;g[2*abs(v)-1][2*u-1]=1;}
		if(u<0&&v>0) {g[2*abs(u)-1][2*v-1]=1;g[2*v][2*abs(u)]=1;}
		if(u<0&&v<0) {g[2*abs(u)-1][2*abs(v)]=1;g[2*abs(v)-1][2*abs(u)]=1;}
	}
}
	

void inverse()
{
	int i,j,k;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
			k=g[i][j];
			g[i][j]=g[j][i];
			g[j][i]=k;
		}
	grt=1;
}

void main()
{
	grt=0;
	input();
    dfs();
    inverse();
    dfs();
}