我最爱的《挑战程序设计竞赛么么哒》上的例题
先放一下2-SAT模板。
也就是给一堆布尔变量（就是要么是真的要么是假的的一堆变量），和一堆布尔方程，问能否通过选择这些变量是真的还是假的，使得所有布尔方程都成立。
注意一下，因为是用scc跑强连通，所以下面这个既是2sat，又是强连通的模板。
强连通还有tarjan方法可以求，这是模板地址tarjan强连通模板
讲一下scc求强连通分量的原理
1、这是原图，这幅图里面ABC属于一个强连通分量
2、跑一遍dfs。终点的序号为1，起点的序号为n。
3、所有的边反向。所以在当初加边的时候！一定要加了正向边，又加上反向边！
4、然后根据序号从大到小处理每个顶点。红的表示正在走，蓝的表示已经走过。
scc函数从顶点六开始走，rdfs函数发现它不存在反向边。那么顶点6独自属于一个强连通分量。
接下来scc函数从顶点五开始走，rdfs函数发现它存在反向边指向6，但是刚刚已经访问过了啦！所以它还是自己属于一个强连通分量。
scc函数从顶点4开始走，rdfs函数发现它反向边的顶点指向一个不曾访问国过的点，那么继续往下rdfs，直到到达某个节点（比如C），它所有反向边指向的节点都访问过了。
5、这样子先dfs一次。再按照序号从大到小逐渐rdfs（也就是反向边的dfs一次），就可以找到所有的强连通分量。
总的复杂度是O（V+E）。
int V;int used[MAX_N];vector<int> vs;int cmp[MAX_N];void dfs(int ver){//printf("ver = %d\n",ver);used[ver] = 1;for (int i = head[ver]; i != -1; i = pra[i].next){int u = pra[i].v;if (!used[u])dfs(u);}vs.push_back(ver);}void rdfs(int ver,int k){//printf("ver = %d k = %d\n",ver,k);used[ver] = 1;cmp[ver] = k;for (int i = rehead[ver]; i != -1; i = re[i].next){int u = re[i].v;if (!used[u])rdfs(u,k);}}int scc(){memset(used,0,sizeof(used));vs.clear();for (int v = 0; v < V; v++){if (!used[v]) dfs(v);}memset(used,0,sizeof(used));int k = 0;for (int i = vs.size()-1; i >= 0; i–){//printf("i=%d vector= %d",i,vs[i]);if (!used[vs[i]])rdfs(vs[i],k++);}return k;}//因为连边之后跑一遍scc，所以记得有反向边的！
题意：有一个神父去主持婚礼，要么在开始的时候主持，要么在结束的时候主持。问你他能否参加小镇上的所有婚礼而不互相冲突。
解答：对于婚礼A，把主持开头设为A为真，把主持结尾设为非A为真。然后呢，根据已知的时间互相连边。连线方向是已知的推出未知。比如已知a和B非不能同时存在，那么a可以推出b，连一个箭头。非b可以推出非a，非b连向非a。
连边完成后跑一遍SCC判断强连通，如果后来A和非A处在同一个强连通分量里面，那就会冲突，反之，输出yes。
对于输出结果。任取一个强连通分量为真，比如对于婚礼a,输出强连通分量标号较大的那个事件就可以了。
上代码
/*注意反向边，反向图，ｉｎｉｔ处理反向的ｈｅａｄ；RE了。算ｎ×ｎ当做边数好了还是RE了。算２ｎ×２ｎ当做边数好了５００００００的ｉｎｔ数组占用三万多的内存。*/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#define MAX_N 10000#define SIZE_M 4000005using namespace std;int N;int S[MAX_N],T[MAX_N],D[MAX_N];struct pp{int v,next,w;}pra[SIZE_M],re[SIZE_M];int e,head[MAX_N],rehead[MAX_N];void init(){e = 0;memset(head,-1,sizeof(head) );memset(rehead,-1,sizeof(rehead) );}void addedge(int x,int y)//,int z1,int z2){pra[e].v = y;pra[e].next = head[x];head[x] = e;re[e].v = x;re[e].next = rehead[y];rehead[y] = e++;}int V;int used[MAX_N];vector<int> vs;int cmp[MAX_N];void dfs(int ver){//printf("ver = %d\n",ver);used[ver] = 1;for (int i = head[ver]; i != -1; i = pra[i].next){int u = pra[i].v;if (!used[u])dfs(u);}vs.push_back(ver);}void rdfs(int ver,int k){//printf("ver = %d k = %d\n",ver,k);used[ver] = 1;cmp[ver] = k;for (int i = rehead[ver]; i != -1; i = re[i].next){int u = re[i].v;if (!used[u])rdfs(u,k);}}int scc(){memset(used,0,sizeof(used));vs.clear();for (int v = 0; v < V; v++){if (!used[v]) dfs(v);}memset(used,0,sizeof(used));int k = 0;for (int i = vs.size()-1; i >= 0; i–){//printf("i=%d vector= %d",i,vs[i]);if (!used[vs[i]])rdfs(vs[i],k++);}return k;}//因为连边之后跑一遍scc，所以记得有反向边的！/*连线方向是已知的推出未知 其他的不用管了哈哈哈哈比如已知a和B非不能同时存在，那么a可以推出b，连一个箭头。非b可以推出非a，非b连向非a2-sat的原理就是。在可以互相发生的事情之间连一条边，然后*/void solve(){//设a是i，，非a是i+N；b是j,非b是b+NV = 2*N;for (int i = 0; i < N; i++)for (int j = 0; j < i; j++){//i > j, 连单向边，两边方式不同//for (int j = 0; j < N; j++){// printf("i=%d j = %d",i,j);if (min(S[i]+D[i], S[j]+ D[j])> max(S[i],S[j])){//由当前的a可以推出b非。由当前的b可以推出a非addedge(i,j+ N);//从上往下连addedge(j,i+N);// 从下往上连//printf("ss i=%d j = %d\n",i,j);}if (min(S[i]+D[i],T[j] )> max(S[i],T[j]- D[j])){//由当前的a可以推出b，由当前的b非可以推出a非addedge(i, j);addedge(j+ N, i + N);//printf("s ti=%d j = %d\n",i,j);}if (min(T[i],T[j])> max(T[i]-D[i],T[j] – D[j])){//由当前的a非可以推出b，由当前的b非可以推出aaddedge(i+N, j);addedge(j+N,i);//printf("tt i=%d j = %d\n",i,j);/*addedge(i,j+ N);addedge(j,i+ N);*/}if (min( T[i],S[j]+ D[j])> max(S[j], T[i] – D[i])){//由当前的a非可以推出b非，由当前的b可以推出aaddedge(i+ N, j+N);addedge(j,i);//printf("tsi=%d j = %d\n",i,j);/*addedge(i,j);addedge(j + N, i + N);*/}}scc();/*for (int i = 0; i < V; i++){//printf("i=%d",i);for (int j = head[i]; j != -1; j = pra[j].next)printf(" %d temp=%d",pra[j].v,cmp[pra[j].v]);puts("");}*/for (int i = 0; i < N; i++)if (cmp[i] == cmp[i+N]){//printf("i=%d\n",i);puts("NO");return;}puts("YES");for (int i = 0; i < N; i++){if (cmp[i] > cmp[i+N]){// 任取一个联通分量设为真。看当前ａ还是非ａ在这个联通分量中printf("%02d:%02d %02d:%02d\n",S[i]/60,S[i]%60,(S[i]+ D[i])/60,(S[i]+ D[i])%60);}elseprintf("%02d:%02d %02d:%02d\n",(T[i] – D[i])/60,(T[i] – D[i])%60,T[i]/60,T[i]%60);}}int main(){//freopen("input.txt","r",stdin);int sum=0;while (~scanf("%d",&N)){init();int temp1,temp2,temp3,temp4,temp5;for (int i = 0; i < N ;i++){scanf("%d:%d %d:%d %d",&temp1,&temp2,&temp3,&temp4,&temp5);S[i] = temp1*60 + temp2;T[i] = temp3 * 60 + temp4;D[i] = temp5;//printf("%d %d %d\n",S[i],T[i],D[i]);}solve();//printf("%d\n",sum++);}return 0;}/*208:00 09:00 3008:15 09:00 20*/
这一生我只牵你的手，因为今生有你早已足够。
