http://poj.org/problem?id=3207
题意：
平面上，一个圆，圆的边上按顺时针放着n个点。现在要连m条边，比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。给你的信息中，每个点最多只会连接的一条边。问能不能连接这m条边，使这些边都不相交。
解题报告：
题意可能刚开始不是很好理解，比如1 5连边，2，6连边，由于点是顺序排列的，一画图就可以发现，这两条边必须一个从圆外面连，一个从内部连，否则就会相交。如果再加入3 7这条边，那么就必须相交了。
这样，就可以转化成标准的2-sta问题：
1：每个边看成2个点：分别表示在内部连接和在外部连接，只能选择一个。计作点i和点i'
2：如果两条边i和j必须一个画在内部，一个画在外部（一个简单判断就可以）
那么连边：
i->j’, 表示i画内部的话，j只能画外部，即j’
j->i’，同理
i’->j，同理
j’->i，同理
然后就是2-sat算法了，tarjan一下，如果有i和i'同属于一个强联通，返回false，否则就成立。
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 100000000
16 #define mx 1<<60
17 #define ll __int64
18 const double pi = acos(-1.0);
19 const int maxn = 300000;
20 using namespace std;
21 int top,num,bcnt,belong[maxn],instack[maxn],stack[maxn],dfn[maxn],low[maxn];
22 int n ,m;
23 struct node
24 {
25 int x,y;
26
27 }a[maxn];
28 struct pnode
29 {
30 int to;
31 int next;
32 }p[maxn];
33
34 int cnt ,next[maxn];
35 void add(int u,int v)
36 {
37 p[cnt].to = v;
38 p[cnt].next = next[u];
39 next[u] = cnt++;
40
41 }
42 void tarjan(int i)
43 {
44 int j,k;
45 dfn[i] = low[i] = ++num;
46 stack[++top] = i;
47 instack[i] = 1;
48 for(k = next[i] ; k != -1;k = p[k].next)
49 {
50
51 j = p[k].to ;
52 if(!dfn[j])
53 {
54 tarjan(j);
55 if(low[j] < low[i]) low[i] = low[j] ;
56 }
57 else
58 {
59 if(instack[j] && dfn[j] < low[i]) low[i] = dfn[j] ;
60 }
61
62 }
63 if(dfn[i] == low[i])
64 {
65 bcnt++;
66 do
67 {
68 j = stack[top--];
69 instack[j] = 0 ;
70 belong[j] = bcnt ;
71 }while(j != i);
72 }
73 }
74 void solve()
75 {
76 int i, l;
77 for(i =0 ; i <= m*2;i++)
78 {
79 dfn[i] = low[i] = instack[i] = stack[i] = belong[i] = 0;
80 }
81 top = bcnt = num = 0;
82 for(i = 0 ; i < 2*m;i++)
83 {
84 if(!dfn[i])tarjan(i);
85 }
86 bool f = true ;
87 for(i = 0 ; i < m;i++)
88 {
89
90 if(belong[i] == belong[i+m])
91 {
92
93 f = false ;
94 break ;
95 }
96 }
97
98 if(f) printf("panda is telling the truth...\n");
99 else
100 printf("the evil panda is lying again\n");
101 }
102 void init()
103 {
104 CL(next,-1);
105 cnt = 0 ;
106
107 }
108 int main()
109 {
110 int i,j;
111 //freopen("data.txt","r",stdin) ;
112 while(scanf("%d%d",&n,&m)!=EOF)
113 {
114 init();
115 for(i = 0 ; i < m;i++)
116 {
117 scanf("%d%d",&a[i].x,&a[i].y);
118 if(a[i].x > a[i].y) swap(a[i].x,a[i].y);
119 }
120 for(i = 0 ; i < m;i++ )
121 {
122 for(j = i+1;j<m;j++)
123 {
124 if(a[i].x < a[j].x && a[j].x < a[i].y &&a[i].y < a[j].y|| a[j].x<a[i].x&&a[i].x < a[j].y &&a[j].y < a[i].y)//判断是否相交
125 {
126 add(i,j + m);
127 add(j + m,i);
128 add(i + m,j);
129 add(j ,i + m) ;
130 }
131 }
132 }
133 solve();
134
135
136 }
137
138 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 100000000
16 #define mx 1<<60
17 #define ll __int64
18 const double pi = acos(-1.0);
19 const int maxn = 300000;
20 using namespace std;
21 int top,num,bcnt,belong[maxn],instack[maxn],stack[maxn],dfn[maxn],low[maxn];
22 int n ,m;
23 struct node
24 {
25 int x,y;
26
27 }a[maxn];
28 struct pnode
29 {
30 int to;
31 int next;
32 }p[maxn];
33
34 int cnt ,next[maxn];
35 void add(int u,int v)
36 {
37 p[cnt].to = v;
38 p[cnt].next = next[u];
39 next[u] = cnt++;
40
41 }
42 void tarjan(int i)
43 {
44 int j,k;
45 dfn[i] = low[i] = ++num;
46 stack[++top] = i;
47 instack[i] = 1;
48 for(k = next[i] ; k != -1;k = p[k].next)
49 {
50
51 j = p[k].to ;
52 if(!dfn[j])
53 {
54 tarjan(j);
55 if(low[j] < low[i]) low[i] = low[j] ;
56 }
57 else
58 {
59 if(instack[j] && dfn[j] < low[i]) low[i] = dfn[j] ;
60 }
61
62 }
63 if(dfn[i] == low[i])
64 {
65 bcnt++;
66 do
67 {
68 j = stack[top--];
69 instack[j] = 0 ;
70 belong[j] = bcnt ;
71 }while(j != i);
72 }
73 }
74 void solve()
75 {
76 int i, l;
77 for(i =0 ; i <= m*2;i++)
78 {
79 dfn[i] = low[i] = instack[i] = stack[i] = belong[i] = 0;
80 }
81 top = bcnt = num = 0;
82 for(i = 0 ; i < 2*m;i++)
83 {
84 if(!dfn[i])tarjan(i);
85 }
86 bool f = true ;
87 for(i = 0 ; i < m;i++)
88 {
89
90 if(belong[i] == belong[i+m])
91 {
92
93 f = false ;
94 break ;
95 }
96 }
97
98 if(f) printf("panda is telling the truth...\n");
99 else
100 printf("the evil panda is lying again\n");
101 }
102 void init()
103 {
104 CL(next,-1);
105 cnt = 0 ;
106
107 }
108 int main()
109 {
110 int i,j;
111 //freopen("data.txt","r",stdin) ;
112 while(scanf("%d%d",&n,&m)!=EOF)
113 {
114 init();
115 for(i = 0 ; i < m;i++)
116 {
117 scanf("%d%d",&a[i].x,&a[i].y);
118 if(a[i].x > a[i].y) swap(a[i].x,a[i].y);
119 }
120 for(i = 0 ; i < m;i++ )
121 {
122 for(j = i+1;j<m;j++)
123 {
124 if(a[i].x < a[j].x && a[j].x < a[i].y &&a[i].y < a[j].y|| a[j].x<a[i].x&&a[i].x < a[j].y &&a[j].y < a[i].y)//判断是否相交
125 {
126 add(i,j + m);
127 add(j + m,i);
128 add(i + m,j);
129 add(j ,i + m) ;
130 }
131 }
132 }
133 solve();
134
135
136 }
137
138 }