记住几个最重要的公式：
xANDy=0<=>(x=>y′)AND(y=>x′)
xANDy=1<=>(x′=>x)AND(y′=>y)
xORy=0<=>(x=>x′)AND(y=>y′)
xORy=1<=>(x′=>y)AND(y′=>x)
xXORy=0<=>(x′=>y′)AND(x=>y)AND(y=>x)AND(y′=>x′)
xXORy=1<=>(x=>y′)AND(x′=>y)AND(y=>x′)AND(y′=>x)
连边 缩环 判一判是不是在一个环里（拓扑输出方案）
POJ 3207
这道题是X xor Y=1的形式
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=;
int n,m,first[N],next[N],v[N],tot,T,cnt,jy,low[N],dfn[N],vis[N],stk[N],top,p[N];
struct Nod{int from,to;}node[N];
void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}
void addedge(int x,int y){add(x+n,y),add(x,y+n),add(y,x+n),add(y+n,x);}
void tarjan(int x){
low[x]=dfn[x]=++cnt;vis[x]=;stk[++top]=x;
for(int i=first[x];~i;i=next[i]){
if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]);
else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]);
}
if(low[x]==dfn[x]){
T++;
do{
jy=stk[top--],vis[jy]=;p[jy]=T;
}while(jy!=x);
}
}
int main(){
memset(first,-,sizeof(first));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",&node[i].from,&node[i].to);
if(node[i].from>node[i].to)swap(node[i].from,node[i].to);
}
for(int i=;i<=m;i++){
for(int j=;j<=m;j++){
if(i!=j&&node[j].from>=node[i].from&&node[j].from<=node[i].to&&node[j].to>=node[i].to)addedge(i,j);
}
}
for(int i=;i<=*n;i++)if(!dfn[i])tarjan(i);
for(int i=;i<=m;i++){
if(p[node[i].from]==p[node[i].to]){puts("the evil panda is lying again");return ;}
}puts("panda is telling the truth...");
}
POJ 3683
如果时间冲突-> X AND Y =0
（有一些trick省略了拓扑）
若缩完环以后i<i+n 就是开始
否则是结束
//By SiriusRen
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=,M=*;
int n,x1,y1,x2,y2,dfn[N],low[N],vis[N],p[N],v[M],next[M],first[N],tot,cnt,stk[N],top,T,jy;
struct Node{int begin,end,last;}node[N];
void add(int x,int y){v[++tot]=y,next[tot]=first[x],first[x]=tot;}
bool check(int a,int b,int c,int d){return !(b<=c||d<=a);}
void tarjan(int x){
dfn[x]=low[x]=++cnt,vis[x]=,stk[++top]=x;
for(int i=first[x];i;i=next[i])
if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]);
else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]);
if(low[x]==dfn[x]){T++;do jy=stk[top--],vis[jy]=,p[jy]=T;while(jy!=x);}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d:%d%d:%d%d",&x1,&y1,&x2,&y2,&node[i].last),
node[i].begin=x1*+y1,node[i].end=x2*+y2;
for(int i=;i<=n;i++)
for(int j=;j<i;j++){
if(check(node[i].begin,node[i].begin+node[i].last,node[j].begin,node[j].begin+node[j].last))add(i,j+n),add(j,i+n);
if(check(node[i].begin,node[i].begin+node[i].last,node[j].end-node[j].last,node[j].end))add(i,j),add(j+n,i+n);
if(check(node[i].end-node[i].last,node[i].end,node[j].begin,node[j].begin+node[j].last))add(i+n,j+n),add(j,i);
if(check(node[i].end-node[i].last,node[i].end,node[j].end-node[j].last,node[j].end))add(i+n,j),add(j+n,i);
}
for(int i=;i<=*n;i++)if(!dfn[i])tarjan(i);
for(int i=;i<=n;i++)if(p[i]==p[i+n]){puts("NO");return ;}
puts("YES");
for(int i=;i<=n;i++){
if(p[i]<p[i+n])printf("%02d:%02d %02d:%02d\n",node[i].begin/,node[i].begin%,(node[i].begin+node[i].last)/,(node[i].begin+node[i].last)%);
else printf("%02d:%02d %02d:%02d\n",(node[i].end-node[i].last)/,(node[i].end-node[i].last)%,node[i].end/,node[i].end%);
}
}