还是那句话，做2SAT题时，找出矛盾点基本上可解了。这道题也是这样

题意是说给出一个圆上的 n 个点（0~n-1编号），然后在指定的 m 对点之间各连一条线（可以在圆内，也可以在圆外，可以是曲线，这点真心坑爹，开始一直木有看明白），然后问你是否能使这些线都不相交

当两条线在同一边会有交点时，即会有矛盾，建图加边。

对于那些没有交点即没有矛盾的边，直接忽略就好，因为边的含义是“必须”。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5   6 const int MAXN=1050;  7 const int MAXM=1000000;  8 int n,m;  9 struct d{ 10     int u,v; 11 }sv[505]; 12 int dfn[MAXN],low[MAXN],st[MAXN],tot,stop,pat,indx,belong[MAXN]; 13 bool stack[MAXN]; 14 struct e{ 15     int u,v; 16     int next; 17 }edge[MAXM]; 18 int head[MAXN]; 19  20 void addedge(int u,int v){ 21     edge[tot].u=u; 22     edge[tot].v=v; 23     edge[tot].next=head[u]; 24     head[u]=tot++; 25 } 26  27 void exch(int &x,int &y){ 28     if(x>y){ 29         int tmp=y; 30         y=x; 31         x=tmp; 32     } 33 } 34  35 bool sure(int i,int k){ 36     int u=sv[k].u; 37     int v=sv[k].v; 38     int p=sv[i].u; 39     int q=sv[i].v; 40     if(p>=u&&p<=v&&q>=u&&q<=v) 41     return false; 42     if(p>=v) return false; 43     if(q<=u) return false; 44     if(p<=u&&q>=v) return false; 45     return true; 46 } 47  48 void tarjan(int u){ 49     dfn[u]=low[u]=++indx; 50     stack[u]=true; 51     st[stop++]=u; 52     int v; 53     for(int e=head[u];e!=-1;e=edge[e].next){ 54         v=edge[e].v; 55         if(dfn[v]==0){ 56             tarjan(v); 57             low[u]=min(low[u],low[v]); 58         } 59         else if(stack[v]){ 60             low[u]=min(low[u],dfn[v]); 61         } 62     } 63     if(dfn[u]==low[u]){ 64         pat++; 65         do{ 66             v=st[--stop]; 67             belong[v]=pat; 68             stack[v]=false; 69         }while(u!=v); 70     } 71 } 72  73 int main(){ 74     int u,v; 75     while(scanf("%d%d",&n,&m)!=EOF){ 76         tot=indx=pat=stop=0; 77         for(int i=0;i
         
          0){ 86                 for(int k=0;k