HDU 3062 Party (2-SAT入門)

題目鏈接：hdu 3062

題面：

Party Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5679????Accepted Submission(s): 1846


Problem Description 有n對夫妻被邀請參加一個(gè)聚會(huì)，因?yàn)閳龅氐膯栴}，每對夫妻中只有1人可以列席。在2n 個(gè)人中，某些人之間有著很大的矛盾（當(dāng)然夫妻之間是沒有矛盾的），有矛盾的2個(gè)人是不會(huì)同時(shí)出現(xiàn)在聚會(huì)上的。有沒有可能會(huì)有n 個(gè)人同時(shí)列席？ ?
Input n： 表示有n對夫妻被邀請 (n<= 1000)
m： 表示有m 對矛盾關(guān)系 ( m < (n - 1) * (n -1))

在接下來的m行中，每行會(huì)有4個(gè)數(shù)字，分別是 A1,A2,C1,C2
A1,A2分別表示是夫妻的編號(hào)
C1,C2 表示是妻子還是丈夫 ，0表示妻子 ，1是丈夫
夫妻編號(hào)從 0 到 n -1
?
Output 如果存在一種情況 則輸出YES
否則輸出 NO
?
Sample Input

2 1 0 1 1 1 ?
Sample Output

YES ?
Source 2009 Multi-University Training Contest 16 - Host by NIT

?
題意：
? ? n對夫妻，某些人之間有矛盾關(guān)系，（夫妻之間不存在矛盾），要求每對夫妻派出一人參加派對，問是否有可行方案。

解題：
? ? 最裸的2-SAT問題，只問是否有解，不要求構(gòu)造方案。假如A，B存在矛盾，那么A如果要參加派對，那么肯定是和B‘一起參加，假如B要參加派對，那么肯定是和A’參加。故加必選邊的時(shí)候，加的是(A->B')和（B->A'），那么是否可以加B'->A或者A'->B呢？答案是否定的，因?yàn)锳，B之間存在矛盾，并不代表B‘和A’之間就存在矛盾，B‘就一定要和A組成共同關(guān)系。以此方式建好圖之后，跑一遍tarjan，看是否有夫妻節(jié)點(diǎn)屬于同一個(gè)聯(lián)通塊，若有則判定無解，若無，則代表有解。（兩個(gè)夫妻節(jié)點(diǎn)屬于同一聯(lián)通塊，即代表他們之間成環(huán)了，選中A，也要選中A‘，自然就矛盾了，故而無解）

代碼：

#include 
#include 
#include 
#define sz 2010
using namespace std;
int cnt=0,p=0,tt=0,sig;
struct edge
{
	int fm,to,nxt;
}store[4000010];
int head[sz],low[sz],dfn[sz],stack[sz],color[sz];
int vis[sz];
//加邊
void addedge(int fm,int to)
{
	store[cnt].nxt=head[fm];
	head[fm]=cnt;
	store[cnt].fm=fm;
	store[cnt++].to=to;
}
//tarjan求強(qiáng)聯(lián)通分量
void tarjan(int x)
{
	int v;
	vis[x]=1;
    dfn[x]=low[x]=p++;
	stack[++tt]=x;
	for(int i=head[x];~i;i=store[i].nxt)
	{
       v=store[i].to;
	   if(vis[v]==0)
		   tarjan(v);
	   if(vis[v]==1)
		   low[x]=min(low[x],low[v]);
	}
	if(dfn[x]==low[x])
	{
		sig++;
		do
		{
			low[stack[tt]]=sig;
			color[stack[tt]]=sig;
			vis[stack[tt]]=-1;
		}
		while(stack[tt--]!=x);
	}
}
int main()
{
	int n,m,a,b,c,d,lim;
	while(~scanf("%d%d",&n,&m))
	{
	  memset(head,-1,sizeof(head));
	  memset(vis,0,sizeof(vis));
      cnt=p=tt=sig=0;
      for(int i=0;i