poj3207:http://poj.org/problem?id=3207
题意：：平面上有一个圆，圆的边上按顺时针放着0..n-1共n个点。现在要连m条边，比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。给你的信息中，每个点最多只能连一条边。问是否可以连接这m条边，使这些边都不相交。
题解：第一道2-sat。看了别人的题解，才理解了这样的想法。对于一条边，要么在圆内要么在圆外。两条相交的边不能同时在园内或者同时在圆外，所以一条在园内，一条在圆外。这样就是2-sat问题了。这一题一定要注意边的数量，不是500，是很大的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=;
const int M=;
struct Node{
int u;
int v;
}e[N*];
struct Edge{
int to,next;
} edge[M]; int n,m,cnt,dep,top,atype;
int dfn[N],low[N],vis[N],head[N],st[N],belong[N],in[N],out[N],sum[N];
//sum[i]记录第i个连通图的点的个数,in[i],out[i],表示缩点之后点的入度和初度。
void init(){
cnt=dep=top=atype=;
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
memset(belong,,sizeof(belong));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
memset(sum,,sizeof(sum));
}
void addedge(int u,int v){
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
} void Tarjan(int u){
dfn[u]=low[u]=++dep;
st[top++]=u;
vis[u]=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
int j;
if(dfn[u]==low[u]){
atype++;
do{
j=st[--top];
belong[j]=atype;
sum[atype]++; //记录每个连通分量中点的个数
vis[j]=;
}
while(u!=j);
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=;i<=m;i++){
scanf("%d%d",&e[i].u,&e[i].v);
}
init();
for(int i=;i<=m;i++){
for(int j=i+;j<=m;j++){
int a=e[i].u;int b=e[i].v;
int c=e[j].u;int d=e[j].v;
if((a<c&&c<b&&b<d)||(c<a&&a<d&&d<b)){
addedge(i,j+m);
addedge(j+m,i);
addedge(j,i+m);
addedge(i+m,j);
}
}
}
for(int i=;i<=m*;i++)
if(!dfn[i])Tarjan(i);
bool flag=false;
for(int i=;i<=m;i++){
if(belong[i]==belong[i+m]){
flag=true;
} }
if(!flag){
printf("panda is telling the truth...\n");
}
else
printf("the evil panda is lying again\n");
}
}