题意

            n个数1~n按顺序围成一个圈...现在在某些两点间加边..边可以加在圈内或者圈外..问是否会发生冲突？如果不发生冲突..输每一条边是放圈内还是圈外.

    题解

            这道题和POJ 3207差不多了..只是那道题只要判断是否存在不要输出方案...发现个很严重的问题..POJ 3207的数据实在是太弱了..我上一个程序里判断两个线段是否相交是个错了..都让我AC了..导致我做这题是沿用了思路...浪费了很多时间...

            先把每条线段看成一个组连个点..圈外和圈内..然后根据线段的冲突关系构造2-sat图..用tarjan做强联通分量判断是否存在方案使得每个线段都不冲突..并且将每个强联通分量缩成一个点,..若存在方案..开始找方案..将缩点后的图构造好..得到的会是一个有向无环图(要是有环那两个强联通分量就应该合并了..所以无环)..按照拓扑排序从入度为0的点进入...对到达的点染色(也就是标记)..并且将对应的一些点也染色(就是同一组的另一个,标记为另一个颜色)...最后根据染色输出每条边的内外..

 

 

Program:

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 205using namespace std; struct node{ int x,y;}line[MAXN];vector
            
              T[MAXN];int dfn[MAXN],low[MAXN],DfsIndex,tpnum,tp[MAXN],color[MAXN];bool instack[MAXN],arc[MAXN][MAXN],d[MAXN];stack
             
               mystack;bool ok(int a,int b){ if (line[a].y>line[b].x && line[a].y
              
               =line[b].x && line[a].x<=line[b].y)) return false; if (line[a].x>line[b].x && line[a].x
               
                =line[b].x && line[a].y<=line[b].y)) return false; return true;}void tarjan(int x){ int i,y,m=T[x].size(); dfn[x]=low[x]=++DfsIndex; instack[x]=true; mystack.push(x); for (i=0;i
                
                 y) t=x,x=y,y=t; line[i].x=x,line[i].y=y; } for (i=0;i<(m<<1);i++) T[i].clear(); for (i=0;i