Ikki's Story IV

题意：：平面上有一个圆，圆的边上按顺时针放着0..n-1共n个点。现在要连m条边，比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。给你的信息中，每个点最多只能连一条边。问是否可以连接这m条边，使这些边都不相交。

题解：第一道2-sat。看了别人的题解，才理解了这样的想法。对于一条边，要么在圆内要么在圆外。两条相交的边不能同时在园内或者同时在圆外，所以一条在园内，一条在圆外。这样就是2-sat问题了。这一题一定要注意边的数量，不是500，是很大的。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 const int N=20002;
 8 const int M=4000002;
 9 struct Node{
10   int u;
11   int v;
12 }e[N*2];
13 struct Edge{
14     int to,next;
15 } edge[M];
16 
17 int  n,m,cnt,dep,top,atype;
18 int  dfn[N],low[N],vis[N],head[N],st[N],belong[N],in[N],out[N],sum[N];
19 //sum[i]记录第i个连通图的点的个数,in[i],out[i],表示缩点之后点的入度和初度。
20 void init(){
21       cnt=dep=top=atype=0;
22     memset(head,-1,sizeof(head));
23     memset(dfn,0,sizeof(dfn));
24     memset(low,0,sizeof(low));
25     memset(vis,0,sizeof(vis));
26     memset(belong,0,sizeof(belong));
27     memset(in,0,sizeof(in));
28     memset(out,0,sizeof(out));
29     memset(sum,0,sizeof(sum));
30 }
31 void addedge(int u,int v){
32     edge[cnt].to=v;
33     edge[cnt].next=head[u];
34     head[u]=cnt++;
35 }
36 
37 void Tarjan(int u){
38     dfn[u]=low[u]=++dep;
39     st[top++]=u;
40     vis[u]=1;
41     for(int i=head[u]; i!=-1; i=edge[i].next){
42         int v=edge[i].to;
43         if(!dfn[v]){
44             Tarjan(v);
45             low[u]=min(low[u],low[v]);
46         }
47         else if(vis[v]){
48             low[u]=min(low[u],dfn[v]);
49         }
50     }
51     int j;
52     if(dfn[u]==low[u]){
53         atype++;
54         do{
55             j=st[--top];
56             belong[j]=atype;
57             sum[atype]++;   //记录每个连通分量中点的个数
58             vis[j]=0;
59         }
60         while(u!=j);
61     }
62 }
63 int main(){
64    while(~scanf("%d%d",&n,&m)){
65        for(int i=1;i<=m;i++){
66           scanf("%d%d",&e[i].u,&e[i].v);
67        }
68        init();
69        for(int i=1;i<=m;i++){
70           for(int j=i+1;j<=m;j++){
71              int a=e[i].u;int b=e[i].v;
72              int c=e[j].u;int d=e[j].v;
73              if((a<c&&c<b&&b<d)||(c<a&&a<d&&d<b)){
74                 addedge(i,j+m);
75                 addedge(j+m,i);
76                 addedge(j,i+m);
77                 addedge(i+m,j);
78              }
79           }
80        }
81        for(int i=1;i<=m*2;i++)
82           if(!dfn[i])Tarjan(i);
83          bool flag=false;
84          for(int i=1;i<=m;i++){
85             if(belong[i]==belong[i+m]){
86                 flag=true;
87             }
88 
89          }
90          if(!flag){
91             printf("panda is telling the truth...
");
92          }
93          else
94            printf("the evil panda is lying again
");
95    }
96 }

View Code