这个题的意思是有一个0-n-1的顺时针圈， 现在想要给这些圈中的两对数字连线，这些连线可以从圈外连也可以从圈内连， 问能不能再连线不相交的情况下连完所有的数对。考虑到每一个数对的连接只有两种可能， 我们将一个数对看成一个集合， 这个集合有两个元素， 一个是从圆内连线， 一个是从圆外连线， 问题就抽象成了普通的2-sat问题，然后就可以构图， 构图完成后求一下将环缩成一个点， 然后判断集合内两个元素有没有同时在一个环内即可， 若是在则无解， 不在则有解。 这个题还需要注意的是判断两对连线相交的方法。 代码如下：
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> using namespace std; const int maxn = 1000+10; int n, m; struct P { int a, b; }p[500+10]; struct Scc { int V; vector<int> G[maxn]; //原始图 vector<int> rG[maxn]; //反向边 vector<int> vs; //后序遍历顶点列表 bool used[maxn]; //访问标记 int cmp[maxn]; //所属强连通分量 void init() { for(int i=0; i<=V; i++) G[i].clear(), rG[i].clear(); } void add_edge(int from, int to) { G[from].push_back(to); rG[to].push_back(from); } void dfs(int v) { used[v] = true; for(int i=0; i<G[v].size(); i++) if(!used[G[v][i]]) dfs(G[v][i]); vs.push_back(v); } void rdfs(int v, int k) { used[v] = true; cmp[v] = k; for(int i=0; i<rG[v].size(); i++) if(!used[rG[v][i]]) rdfs(rG[v][i], k); } int scc() { memset(used, 0, sizeof(used)); vs.clear(); for(int v=1; v<=V; v++) if(!used[v]) dfs(v); memset(used, 0, sizeof(used)); int k = 1; for(int i=vs.size()-1; i>=0; i--) if(!used[vs[i]]) rdfs(vs[i], k++); return k-1; } }ss; int main() { scanf("%d%d", &n, &m); for(int i=1; i<=m; i++) { int a, b; scanf("%d%d", &a, &b); if(a>b) swap(a, b); p[i] = (P){a, b}; } ss.V = 2*m; ss.init(); for(int i=1; i<=m; i++) for(int j=i+1; j<=m; j++) { if((p[i].a>p[j].a&&p[i].a<p[j].b&&p[i].b>p[j].b)|| (p[i].b>p[j].a&&p[i].b<p[j].b&&p[i].a<p[j].a)) { ss.add_edge(2*i-1, 2*j); ss.add_edge(2*j, 2*i-1); ss.add_edge(2*i, 2*j-1); ss.add_edge(2*j-1, 2*i); } } ss.scc(); bool res = true; for(int i=1; i<=m; i++) if(ss.cmp[2*i-1]==ss.cmp[2*i]) { res = false; break; } if(res) printf("panda is telling the truth... "); else printf("the evil panda is lying again"); return 0; }