学步园

简单2-SAT问题,拆点，回家i，不回家i+n*3；

建好队长跟队员之间的关系，每对队员之间的关系，

判断每个队员回不回家是否矛盾

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