题意：平面上，一个圆，圆的边上按顺时针放着n个点。现在要连m条边，比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。给你的信息中，每个点最多只会连接的一条边。问能不能连接这m条边，使这些边都不相交。
分析：将每一条边缩成一个点，对于每条边要么在圆内要么在园外只有满足一种情况，将在圆内设为i，在圆外设为i',那么对于两条线（i, j）不能同时在圆内，那么也不能同时在圆外。则有四种情况 （i, j') (i', j) (j, i') (j', i)要建这四条边，然后就照着刘汝佳书上的抄了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <stack>
#include <algorithm>
using namespace std;
const int Max = ;
struct TWOSAT
{
int n;
vector<int> G[Max * ];
bool mark[Max * ];
int S[Max * ], c;
void init(int n)
{
this->n = n;
for (int i = ; i <= n * ; i++)
G[i].clear();
memset(mark, , sizeof(mark));
}
void add_clause(int x, int y)
{
G[ * x].push_back( * y + ); //四条边
G[ * x + ].push_back( * y);
G[ * y + ].push_back( * x);
G[ * y].push_back( * x + );
}
bool dfs(int x)
{
if (mark[x ^ ])
return false;
if (mark[x])
return true;
mark[x] = true;
S[c++] = x;
for (int i = ; i < (int) G[x].size(); i++)
if (!dfs(G[x][i]))
return false;
return true;
}
bool solve()
{
for (int i = ; i <= n * ; i += )
{
if (!mark[i] && !mark[i + ])
{
c = ;
if (!dfs(i))
{
while (c > )
mark[ S[--c] ] = false;
if (!dfs(i + ))
return false;
}
}
}
return true;
}
};
struct Node
{
int s, t;
}node[Max];
int main()
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = ; i <= m; i++)
{
scanf("%d%d", &node[i].s, &node[i].t);
if (node[i].s > node[i].t) //这一步让判断相交很方便
swap(node[i].s, node[i].t);
}
TWOSAT twosat;
twosat.init(m);
for (int i = ; i <= m; i++)
{
for (int j = i + ; j <= m; j++)
{
if ( (node[i].s < node[j].s && node[i].t < node[j].t && node[i].t > node[j].s) || (node[j].s < node[i].s && node[i].t > node[j].t && node[j].t > node[i].s) ) //相交的情况， i 的起点 在 j 的 起点和终点之间并且i的终点要大于j的终点， 另一种情况类似
{
twosat.add_clause(i, j);
}
}
}
if (twosat.solve())
printf("panda is telling the truth...\n");
else
printf("the evil panda is lying again\n");
}
}