POJ 3207
题意：平面上，一个圆，圆的边上按顺时针放着n个点。现在要连m条边，
比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。
给你的信息中，每个点最多只会连接的一条边。问能不能连接这m条边，
使这些边都不相交。
思路：对于每条Link，要么在圆外，要么在圆内，且不可同时满足，
只能两者取一，判断这M条Link是否合法，也就是M条Link不冲突，
这就是典型的2-sat问题了。 将每条Link i 看做一个点，如果Link在圆内，
则选做i ，如果在圆外， 则选做i'。对于两条线(i,j) ，如果i，j不能同时
在圆内，也就可以推出两者不能同时在圆外，这个证明很容易，读者可
以自行证明。i, j不能同时在圆内，则有边(i, j') 、(j ,i')、(i'，j)、(j' ,i)
(这是由2-sat的构图方式决定的，具体可以看《由对称性解2-SAT问题》
这篇论文）。建图完了之后，本题就是判断2-sat问题是否有解，
先求原图的强连通分量，并缩点，(这里我们称：(i,i')属于同一组)，
判断是否存在(i,i')属于同一组，若存在，则不可能，若不存在则可能。
C++代码一
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN 1005
#define MAXM 2000005
#define INF 1000000000
using namespace std;
int n, m, e, head[MAXN];
int dfn[MAXN], low[MAXN], index, instack[MAXN], scc;
int top, st[MAXN], fa[MAXN];
int x[MAXN], y[MAXN];
struct Edge
{
int v, next;
}edge[MAXM];
void init()
{
e = index = scc = top = 0;
memset(dfn, 0, sizeof(dfn));
memset(instack, 0, sizeof(instack));
memset(head, -1, sizeof(head));
}
void insert(int x, int y)
{
edge[e].v = y;
edge[e].next = head[x];
head[x] = e++;
}
void tarjan(int u)
{
int v;
instack[u] = 1;
st[++top] = u;
dfn[u] = low[u] = ++index;
for(int i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].v;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(instack[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
scc++;
do
{
v = st[top--];
instack[v] = 0;
fa[v] = scc;
}while(v != u);
}
}
void build()
{
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &x[i], &y[i]);
x[i]++; y[i]++;
if(x[i] > y[i]) swap(x[i], y[i]);
}
for(int i = 1; i <= m; i++)
for(int j = i + 1; j <= m; j++)
//通过判断得出 两条线的关系,如果通过判断只能一条在内一条在外，就连边
if((x[i] <= x[j] && y[i] >= x[j] && y[i] <= y[j]) || (x[i] >= x[j] && x[i] <= y[j] && y[i] >= y[j]))
{
insert(i, j + m);
insert(j, i + m);
insert(i + m, j);
insert(j + m, i);
}
n = 2 * m;
}
bool check()
{
for(int i = 1; i <= m; i++)
if(fa[i] == fa[i + m]) return false;
return true;
}
void solve()
{
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i);
if(check()) printf("panda is telling the truth...
");
else printf("the evil panda is lying again
");
}
int main()
{
scanf("%d%d", &n, &m);
init();
build();
solve();
return 0;
}
C++代码二
点击
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int nmax = 1e5 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ull p = 67;
const ull MOD = 1610612741;
int n, m, cnt;
typedef pair<int , int > pii;
pii line[nmax];
struct edge {
int to, nxt;
};
struct graph {
int tot, head[nmax];
edge e[(int)1e6 + 7];
void init() {
tot = 0;
memset(head, -1, sizeof head);
}
void add_edge(int u, int v) {
e[tot].to = v;
e[tot].nxt = head[u];
head[u] = tot ++;
}
}g;
inline bool checkcross(pii a, pii b) {
if(a.first <= b.first && a.second >= b.first && a.second <= b.second)
return true;
else if(b.first <= a.first && b.second >= a.first && b.second <= a.second)
return true;
else if(a.first >= b.first && a.first <= b.second && a.second >= b.second)
return true;
else if(b.first >= a.first && b.first <= a.second && b.second >= a.second)
return true;
else
return false;
}
int dfn[nmax], low[nmax], dfs_clock, color[nmax], scc;
int ss[nmax], st;
bool instack[nmax];
void tarjan(int u, const graph & g) {
dfn[u] = low[u] = ++dfs_clock;
ss[st++] = u;
instack[u] = true;
for(int i = g.head[u]; i != -1; i = g.e[i].nxt) {
int v = g.e[i].to;
if(!dfn[v]) {
tarjan(v, g);
low[u] = min(low[u], low[v]);
} else if (instack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]) {
scc++;
int tmp;
while(true) {
tmp = ss[--st];
color[tmp] = scc;
instack[tmp] = false;
if(tmp == u)
break;
}
}
}
bool check() {
for(int i = 1; i <= m; ++i) {
if(color[i] == color[i+m])
return false;
}
return true;
}
void init() {
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(color, 0, sizeof color);
// memset(instack, 0, sizeof instack);
scc = dfs_clock = st;
g.init();
}
int main(){
while(scanf("%d %d", &n, &m) != EOF) {
init();
int a, b;
for(int i = 1; i <= m; ++i) {
scanf("%d %d", &a, &b);
if(a < b) {
line[i].first = a;
line[i].second = b;
} else {
line[i].first = b;
line[i].second = a;
}
}
for(int i = 1; i <= m ;++i) {
for(int j = i + 1; j <= m; ++j) {
if(checkcross(line[i], line[j])) {
g.add_edge(i, j + m);
g.add_edge(i + m, j);
g.add_edge(j, i + m);
g.add_edge(j + m, i);
}
}
}
for(int i = 1; i <= 2 * m; ++i) {
if(!dfn[i])
tarjan(i, g);
}
if(check()) {
printf("panda is telling the truth...
");
} else {
printf("the evil panda is lying again
");
}
}
return 0;
}