http://poj.org/problem?id=3207
有一个环，上有n个点，需要添加m条边（给出的边满足每个点最多连一条边）给出m条边的两个顶点，求是否有方案连边方案使得m条边不相交。
题解：任意两条边如果都在环外一定相交，那么都在环里也一定相交，所以找出一定相交的边，这两条边一定一个在圆里一个在圆外，即 i xor j = 1 。
然后建2 sat图就可以了。
http://blog.sina.com.cn/s/blog_64675f540100k2xj.html 建图方法（有点像点亮苟鈤的数字人生的过程）。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 const int maxn=1010; 8 int n,m; 9 int a[maxn][2]={}; 10 struct nod{ 11 int y,next; 12 }e[maxn*maxn]; 13 int head[maxn]={},tot=0; 14 int dfn[maxn]={},low[maxn]={},bel[maxn]={},sta[maxn]={},vis[maxn]={},cnt,tly,tn; 15 inline void init(int x,int y){e[++tot].y=y;e[tot].next=head[x];head[x]=tot;} 16 void dfs(int x){ 17 dfn[x]=low[x]=++cnt;vis[x]=1;sta[++tly]=x; 18 for(int i=head[x];i;i=e[i].next){ 19 if(!dfn[e[i].y]){ 20 dfs(e[i].y); low[x]=min(low[x],low[e[i].y]); 21 } 22 else if(vis[e[i].y])low[x]=min(low[x],dfn[e[i].y]); 23 } 24 if(low[x]==dfn[x]){ 25 ++tn;int i; 26 do{ 27 i=sta[tly];tly--; 28 vis[i]=0; 29 bel[i]=tn; 30 }while(i!=x); 31 } 32 } 33 int main(){ 34 while(~scanf("%d%d",&n,&m)){ 35 for(int i=1;i<=m;i++){scanf("%d%d",&a[i][0],&a[i][1]);if(a[i][1]<a[i][0])swap(a[i][1],a[i][0]);} 36 for(int i=1;i<=m;i++){ 37 for(int j=i+1;j<=m;j++){ 38 if((a[i][0]<=a[j][1]&&a[i][0]>=a[j][0]&&a[i][1]>=a[j][1])|| 39 (a[j][0]<=a[i][1]&&a[j][0]>=a[i][0]&&a[j][1]>=a[i][1])){ 40 init(2*i-1,2*j);init(2*j-1,2*i); 41 init(2*j,2*i-1);init(2*i,2*j-1); 42 } 43 } 44 } 45 memset(dfn,0,sizeof(dfn)); 46 memset(low,0,sizeof(low)); 47 memset(vis,0,sizeof(vis)); 48 cnt=tn=0; 49 for(int i=1;i<=2*m;i++){ 50 if(!dfn[i])dfs(i); 51 }int f=1; 52 for(int i=1;i<2*m;i+=2){ 53 if(bel[i]==bel[i+1]){ 54 f=0;break; 55 } 56 } 57 if(f) printf("panda is telling the truth... "); 58 else printf("the evil panda is lying again "); 59 } 60 return 0; 61 }