Problem Description
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
Input
n： 表示有n对夫妻被邀请 (n<= 1000)
m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))
m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))
在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫
夫妻编号从 0 到 n -1
Output
如果存在一种情况 则输出YES
否则输出 NO
否则输出 NO
思路：2-SAT模版题，分别要求夫妻必上一个、仇人不能同时上
两个代码，第一个是普通的搜索，第二个是tarjan的解法，第一个593MS，第二个625MS（难道写挫了。。。？），（好吧用改一下第二个代码用C++交变成了312MS……）
#include <cstdio>
#include <cstring>
using namespace std; const int MAXN = ;
const int MAXM = **; struct TwoSAT{
int n, ecnt;
bool mark[MAXN];
int St[MAXN], c;//手动栈
int head[MAXN];
int next[MAXM], to[MAXM]; bool dfs(int x){
if(mark[x^]) return false;
if(mark[x]) return true;
mark[x] = true;
St[c++] = x;
for(int p = head[x]; p; p = next[p])
if(!dfs(to[p])) return false;
return true;
} void init(int n){
this->n = n;
ecnt = ;
memset(head,,sizeof(head));
memset(mark,,sizeof(mark));
} void addEdge1(int x, int y){//x*y=false
to[ecnt] = y^; next[ecnt] = head[x]; head[x] = ecnt++;
to[ecnt] = x^; next[ecnt] = head[y]; head[y] = ecnt++;
} void addEdge2(int x, int y){//x+y=true
to[ecnt] = y; next[ecnt] = head[x^]; head[x^] = ecnt++;
to[ecnt] = x; next[ecnt] = head[y^]; head[y^] = ecnt++;
} bool solve(){
for(int i = ; i < n*; i += )
if(!mark[i] && !mark[i+]){
c = ;
if(!dfs(i)) {
while(c>) mark[St[--c]] = false;
if(!dfs(i^)) return false;
}
}
return true;
}
} G; int main(){
int n, m, a, b, c, d;
while(scanf("%d%d",&n,&m)!=EOF){
G.init(n);
for(int i = ; i < n; ++i) G.addEdge2(i*,(i+n)*);
while(m--){
scanf("%d%d%d%d",&a,&b,&c,&d);
G.addEdge1((a + n*c)*, (b + n*d)*);
}
if(G.solve()) printf("YES\n");
else printf("NO\n");
}
return ;
}
#include <cstdio>
#include <cstring>
using namespace std; const int MAXN = ;
const int MAXM = **; struct TwoSAT{
int n, ecnt, dfs_clock, scc_cnt;
int St[MAXN], c;//手动栈
int head[MAXN], lowlink[MAXN], pre[MAXN], sccno[MAXN];
int next[MAXM], to[MAXM]; void dfs(int u){
pre[u] = lowlink[u] = ++dfs_clock;
St[++c] = u;
for(int p = head[u]; p; p = next[p]){
int &v = to[p];
if(!pre[v]){
dfs(v);
if(lowlink[u] > lowlink[v]) lowlink[u] = lowlink[v];
}else if(!sccno[v]){
if(lowlink[u] > pre[v]) lowlink[u] = pre[v];
}
}
if(lowlink[u] == pre[u]){
scc_cnt++;
while(true){
int x = St[c--];
sccno[x] = scc_cnt;
if(x == u) break;
}
}
} void init(int n){
this->n = n;
ecnt = ; dfs_clock = scc_cnt = ;
memset(head,,sizeof(head));
memset(sccno,,sizeof(sccno));
memset(pre,,sizeof(pre));
} void addEdge1(int x, int y){//x*y=false
to[ecnt] = y^; next[ecnt] = head[x]; head[x] = ecnt++;
to[ecnt] = x^; next[ecnt] = head[y]; head[y] = ecnt++;
} bool solve(){
for(int i = ; i < n; ++i)
if(!pre[i]) dfs(i);
for(int i = ; i < n; i += )
if(sccno[i] == sccno[i^]) return false;
return true;
}
} G; int main(){
int n, m, a, b, c, d;
while(scanf("%d%d",&n,&m)!=EOF){
G.init(*n);
while(m--){
scanf("%d%d%d%d",&a,&b,&c,&d);
G.addEdge1(a* + c, b* + d);
}
if(G.solve()) printf("YES\n");
else printf("NO\n");
}
return ;
}
tarjan