题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=3062
题目大意：
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
分析：
03年论文中所述的典型2-SAT题，按论文中所述构图方式即可：
Addedge( a1+a1+c1, a2+a2+(c2^1) );
Addedge( a2+a2+c2, a1+a1+(c1^1) );
由于 c1，c2即丈夫与妻子的标记分别是0，1所以采用异或取反。再用Tarjan求强连通分量即可。
代码：
hdu3062
1 /*2012-04-24 11:33:12 Accepted 3062 437MS 1040K 1904 B C++*/ 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <vector> 8 using namespace std; 9 10 #define mpair make_pair 11 #define pii pair<int,int> 12 #define MM(a,b) memset(a,b,sizeof(a)); 13 typedef long long lld; 14 typedef unsigned long long u64; 15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;} 16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;} 17 #define maxn 2020 18 19 int n,m; 20 vector<int> adj[maxn]; 21 22 int Bcnt, Top, Index; 23 int stack[maxn], belong[maxn]; 24 bool instack[maxn]; 25 int low[maxn], dfn[maxn]; 26 void Tarjan(int u){ 27 low[u]= dfn[u]= ++Index; 28 stack[++Top]= u; 29 instack[u]=1 ; 30 for(int i=0;i<adj[u].size();++i){ 31 int v= adj[u][i]; 32 if( !dfn[v] ){ 33 Tarjan(v); 34 up_min( low[u], low[v] ); 35 } 36 else if( instack[v] ) 37 up_min( low[u], dfn[v] ); 38 } 39 if( low[u]==dfn[u] ){ 40 Bcnt++; 41 int v; 42 do{ 43 v= stack[Top--]; /// Top--; 44 instack[v]= 0; 45 belong[v]= Bcnt; 46 }while( u!=v ); 47 } 48 } 49 50 int main() 51 { 52 while( cin>>n>>m ){ 53 for(int i=0;i<n+n;++i) adj[i].clear(); 54 while(m--){ 55 int a,b,c,d; 56 scanf("%d%d%d%d", &a, &b, &c, &d); 57 //++a, ++b; 58 adj[a+a+c].push_back( b+b+ (d^1) ); 59 adj[b+b+d].push_back( a+a+ (c^1) ); 60 } 61 62 Bcnt= Index= Top= 0; 63 for(int i=0;i<n+n;++i) dfn[i]= low[i]= instack[i]= 0; 64 for(int i=0;i<n+n;++i) 65 if( !dfn[i] ) 66 Tarjan( i ); 67 68 for(int i=0;i<n+n;i+=2){ 69 if( belong[ i ] == belong[ i+1 ] ){ 70 puts("NO"); 71 break; 72 } 73 if( i==n+n-2 ) puts("YES"); /// i==n+n-2; 74 } 75 } 76 }