2017.2.23[hdu1814]Peaceful Commission(2-SAT)

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #define N 8010
  7 #define M 20010
  8 #define RG register
  9 using namespace std;
 10 bool used[2*N],vis[N][N];
 11 int a,b,h,m,n,t,siz,tim,top,q[2*N],du[2*N],dfn[2*N],dot[2*N],low[2*N],sta[2*N];
 12 struct node{
 13     int cnt,head[2*N];
 14     struct edge{
 15     int to,next;
 16     }e[2*M];
 17     inline void add(int from,int to){
 18     e[++cnt].next=head[from];
 19     e[cnt].to=to;
 20     head[from]=cnt;
 21     }
 22 }pic[2];
 23 inline int gi(){
 24     RG int x=0;RG char c=getchar();
 25     while(c<'0'||c>'9') c=getchar();
 26     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
 27     return x;
 28 }
 29 inline int Abs(RG const int &a){return a>0?a:-a;}
 30 inline int Max(RG const int &a,RG const int &b){return a>b?a:b;}
 31 inline int Min(RG const int &a,RG const int &b){return a>b?b:a;}
 32 inline void tarjian(RG int now){
 33     sta[++top]=now;
 34     low[now]=dfs[now]=++tim;
 35     RG int cnm=pic[0].head[now];
 36     while(cnm){
 37     if(!dfn[pic[0].e[cnm].to]){
 38         dfs(pic[0].e[cnm].to);
 39         low[now]=Min(low[e[cnm].to],low[now]);
 40     }
 41     else if(dfn[pic[0].e[cnm].to]<dfn[now]-1)
 42         low[now]=Min(low[now],dfn[pic[0].e[cnm].to]);
 43     cnm=pic[0].e[cnm].next;
 44     }
 45     if(low[now]==dfn[now]){
 46     dot[now]=++siz;
 47     while(sta[top]!=now)
 48         dot[sta[top--]]=siz;
 49         --top;
 50     }
 51 }
 52 inline void topsort(){
 53     while(h<t){
 54     RG int now=q[++h],cnm=pic[1].head[now];
 55     while(cnm){
 56         if(!--du[pic[1].e[cnm].to])
 57         q[++t]=pic[1].e[cnm].to;
 58         cnm=pic[1].e[cnm].next;
 59     }
 60     }
 61 }
 62 inline void work(){
 63     h=t=siz=tim=0;
 64     memset(du,0,sizeof(du));
 65     memset(dfn,0,sizeof(dfn));
 66     memset(dot,0,sizeof(dot));
 67     memset(low,0,sizeof(low));
 68     memset(pic,0,sizeof(pic));
 69     memset(vis,0,sizeof(vis));
 70     memset(used,0,sizeof(used));
 71     if(m)
 72         for (RG int i=1;i<=m;++i){
 73         a=gi()-1;b=gi()-1;
 74         pic[0].add(a,b^1);
 75         pic[0].add(b,a^1);
 76         }
 77     tarjian(0);
 78     for (RG int i=0;i+=2;i<2*n)
 79     if(dot[i]==dot[i+1]){
 80         putchar('N');
 81         putchar('I');
 82         putchar('E');
 83         putchar('
');
 84         return;
 85     }
 86     for (RG int i=0;i<2*n;++i){
 87     RG int cnm=pic[0].head[i];
 88     while(cnm){
 89         if(!vis[dot[i]][dot[pic[0].e[cnm].to]]){
 90         pic[1].add(dot[i],dot[pic[0].e[cnm].to]);
 91         ++du[dot[pic[0].e[cnm].to]];
 92         }
 93         vis[dot[i]][dot[pic[0].e[cnm].to]]=1;
 94         cnm=pic[0].e[cnm].next;
 95     }
 96     }
 97     for (RG int i=1;i<=siz;++i)
 98     if(!du[i])
 99         q[++t]=i;
100     topsort();
101     tri(q[1]);
102     for (RG int i=0;i<2*n;++i)
103     if(used[i])
104         printf("%d
",i+1);
105 }
106 int main(){
107     freopen("1814.in","r",stdin);
108     freopen("1814.out","w",stdout);
109     while(scanf("%d%d",&n,&m)!=EOF) work();
110     fclose(stdin);
111     fclose(stdout);
112     return 0;
113 }
View Code