【Description】
liympanda, one of Ikki’s friend, likes playing games with Ikki. Today after minesweeping with Ikki and winning so many times, he is tired of such easy games and wants to play another game with Ikki.
liympanda has a magic circle and he puts it on a plane, there are n points on its boundary in circular border: 0, 1, 2, …, n − 1. Evil panda claims that he is connecting m pairs of points. To connect two points, liympanda either places the link entirely inside the circle or entirely outside the circle. Now liympanda tells Ikki no two links touch inside/outside the circle, except on the boundary. He wants Ikki to figure out whether this is possible…
Despaired at the minesweeping game just played, Ikki is totally at a loss, so he decides to write a program to help him.
【Input】
The input contains exactly one test case.
In the test case there will be a line consisting of of two integers: n and m (n ≤ 1,000, m ≤ 500). The following m lines each contain two integers ai and bi, which denote the endpoints of the ith wire. Every point will have at most one link.
【Output】
Output a line, either “panda is telling the truth...” or “the evil panda is lying again”.
【Sample Input】
4 20 13 2
【Sample Output】
panda is telling the truth... --------------------------------------------------------------------------------------------------------------------------- 【题目大意】 平面上一个圆，圆的边上按顺时针放着0~n-1共n个点。连m条边，每条边可以从圆内连接，可以从圆外连接。给出的信息中，每个点最多只会连接一条边。 问能不能连接这m条边，是之互不相交。 【题解】 同样是一道2-SAT问题。把边看成点。把第i条边拆成i和i+m两条边，i表示从圆内部连接，i+m表示从圆外连接。然后根据两条边在内部是否相交判断矛盾关系，由矛盾推出建图方式。具体见代码：
1 #include2 #include 3 #include 4 using namespace std; 5 #define MAXN 1020 6 #define MAXM 520*2 7 struct node 8 { 9 int v; 10 node *next; 11 }; 12 node edge[MAXM*MAXM]; 13 node *cnt=&edge[0]; 14 node *adj[MAXM]; 15 struct Lines 16 { 17 int st,ed; 18 }mat[MAXM/2]; 19 int n,m; 20 int dfn[MAXM],low[MAXM],dcnt; 21 int stack[MAXM],top; 22 int Belong[MAXM],scc; 23 bool Instack[MAXM]; 24 inline void Addedge(int u,int v) 25 { 26 node *p=++cnt; 27 p->v=v; 28 p->next=adj[u]; 29 adj[u]=p; 30 31 p=++cnt; 32 p->v=u; 33 p->next=adj[v]; 34 adj[v]=p; 35 } 36 inline void Get_int(int &Ret) 37 { 38 char ch; 39 bool flag=false; 40 for(;ch=getchar(),ch<'0'||ch>'9';) 41 if(ch=='-') 42 flag=true; 43 for(Ret=ch-'0';ch=getchar(),ch>='0'&&ch<='9';Ret=Ret*10+ch-'0'); 44 flag&&(Ret=-Ret); 45 } 46 inline bool Check(int i,int j) 47 { 48 if(mat[i].st<=mat[j].st&&mat[j].st<=mat[i].ed&&mat[i].ed<=mat[j].ed) 49 return true; 50 if(mat[j].st<=mat[i].st&&mat[i].st<=mat[j].ed&&mat[j].ed<=mat[i].ed) 51 return true; 52 return false; 53 } 54 inline void Read() 55 { 56 //Get_int(n); 57 Get_int(m); 58 int i,j; 59 for(i=1;i<=m;i++) 60 { 61 Get_int(mat[i].st); 62 Get_int(mat[i].ed); 63 if(mat[i].st>mat[i].ed) 64 swap(mat[i].st,mat[i].ed); 65 } 66 for(i=1;i<=m;i++) 67 for(j=i+1;j<=m;j++) 68 if(Check(i,j)) 69 { 70 Addedge(i,j+m); 71 Addedge(i+m,j); 72 } 73 } 74 void Tarjan(int u) 75 { 76 int v; 77 dfn[u]=low[u]=++dcnt; 78 Instack[u]=true; 79 stack[++top]=u; 80 for(node *p=adj[u];p;p=p->next) 81 { 82 v=p->v; 83 if(!dfn[v]) 84 { 85 Tarjan(v); 86 low[u]=min(low[u],low[v]); 87 } 88 else if(Instack[v]) 89 low[u]=min(low[u],dfn[v]); 90 } 91 if(dfn[u]==low[u]) 92 { 93 scc++; 94 do 95 { 96 v=stack[top]; 97 top--; 98 Instack[v]=false; 99 Belong[v]=scc;100 }while(v!=u);101 }102 }103 bool Work()104 {105 int i;106 for(i=1;i<=m*2;i++)107 if(!dfn[i])108 Tarjan(i);109 for(i=1;i<=m;i++)110 if(Belong[i]==Belong[i+m])111 return false;112 return true;113 }114 inline void Print()115 {116 if(Work())117 printf("panda is telling the truth...\n");118 else119 printf("the evil panda is lying again\n");120 }121 inline void Pre()122 {123 memset(edge,0,sizeof(edge));124 memset(adj,0,sizeof(adj));125 cnt=&edge[0];126 memset(dfn,0,sizeof(dfn));127 memset(low,0,sizeof(low));128 dcnt=0;129 memset(Belong,0,sizeof(Belong));130 scc=0;131 memset(stack,0,sizeof(stack));132 top=0;133 memset(Instack,false,sizeof(Instack));134 }135 int main()136 {137 while(scanf("%d",&n)!=EOF)138 {139 Pre();140 Read();141 Print();142 }143 return 0;144 }
此题较之之前那道2-SAT的题目——Poi 0106 和平委员会 要简单一些，因为结果只是判断是否可行，并不需要生成可行解，所以不需要拓扑排序。只是在缩图之后判断一些是否合法即可。