学步园

简单2-SAT问题，看了一下网上的资料， 强连通分量的更深层次的应用，

目前只知道这样求，具体算法的原理还有点模糊，下去应该好好看看，，，

#include<stdio.h>
#include<string.h>
#include<stack>
#define N 2010
using namespace std;
int n,m,low[N],dfs[N],belong[N],ins[N],idx,ans;
struct Eage
{
	int ed;
	Eage *next;
}*eage[N];
void addeage(int x,int y)
{
	Eage *p=new Eage;
	p->ed=y;
	p->next=eage[x];
	eage[x]=p;
}
stack<int>Q;
void Tarjan(int x)  
{  
    int v;  
    low[x]=dfs[x]=idx++;  
    Q.push(x);  
    ins[x]=1;  
    for(Eage *p=eage[x];p;p=p->next)  
    {  
        if(dfs[p->ed]==-1)  
        {  
            Tarjan(p->ed);  
            low[x]=low[x]>low[p->ed]?low[p->ed]:low[x];  
        }  
        else if(ins[p->ed]==1)  
            low[x]=low[x]>dfs[p->ed]?dfs[p->ed]:low[x];  
    }  
    if(dfs[x]==low[x])  
    {  
          
        while(1)  
        {  
            v=Q.top();  
            Q.pop();  
            belong[v]=ans;  
            ins[v]=0;
            if(v==x)break;  
        }  
        ans++;    
    }  
}  
int main()
{
	int i,x,y,a,b,p,q;
	while(scanf("%d",&n)!=-1)
	{
		memset(eage,NULL,sizeof(eage));
		memset(dfs,-1,sizeof(dfs));
		memset(ins,0,sizeof(ins));
		scanf("%d",&m);
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d%d",&x,&y,&a,&b);
			x=x*2+a;
			y=y*2+b;
			if(a==0)
			p=x+1;
			else p=x-1;
			if(b==0)
				q=y+1;
			else q=y-1;
			addeage(x,q);
			addeage(y,p);
		}
		idx=ans=0;
		for(i=0;i<2*n;i++)
		{
			if(dfs[i]==-1)
				Tarjan(i);
		}
		for(i=0;i<n;i++)
		{
			a=i*2;
			b=i*2+1;
			if(belong[a]==belong[b])
				break;
		}
		if(i==n)
			printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}