POJ 3648 Wedding(2-ST)

题目链接：http://poj.org/problem?id=3648

题意：有n对夫妇（编号0到n-1），这些人中有m对人有暧昧关系。现在这些人坐成两排，要求：

1、每对夫妇两个人不能坐在一排；

2、有暧昧关系的人不能都坐在0号新娘的对面。

如果存在满足上述条件的坐法，输出和0号新娘坐在一排的人；否则输出bad luck。

思路：

（1）i:i号新娘在左边

（2）i+n:i号丈夫在左边

（3）i+2*n:i号新娘在右边

（4）i+3*n:i号丈夫在右边 

 #include <stdio.h>
 #include <string.h>
 #include <stack>
 #define min(x,y) ((x)<(y)?(x):(y))
 using namespace std;
 
 struct node
 {
     int v,next;
 };
 
 
 
 const int MAX=1005;
 const int MAXE=100005;
 node edges[MAXE];
 int head[MAX],e;
 int dfn[MAX],low[MAX],visit[MAX],color[MAX],col[MAX];
 int n,m,index,cnt;
 stack<int> S;
 int deg[MAX],ans[MAX],p[MAX];
 int head1[MAX],e1;
 node edges1[MAXE];
 
 
 
 void Add(int u,int v)
 {
     edges[e].v=v;
     edges[e].next=head[u];
     head[u]=e++;
 }
 
 void Add1(int u,int v)
 {
     edges1[e1].v=v;
     edges1[e1].next=head1[u];
     head1[u]=e1++;
 }
 
 void Tarjan(int u)
 {
     int i,v;
 
     low[u]=dfn[u]=++index;S.push(u);visit[u]=1;
     for(i=head[u];i!=-1;i=edges[i].next)
     {
         v=edges[i].v;
         if(!dfn[v])
         {
             Tarjan(v);
             low[u]=min(low[u],low[v]);
         }
         else if(visit[v]) low[u]=min(low[u],dfn[v]);
     }
     if(dfn[u]==low[u])
     {
         cnt++;
         do
         {
             v=S.top();
             S.pop();
             visit[v]=0;
             color[v]=cnt;
         }while(u!=v);
     }
 }
 
 void init(int n)
 {
     memset(deg,0,sizeof(deg));
     memset(head1,-1,sizeof(head1));
     e1=0;
     int i,u,v,x,y;
     for(u=0;u<2*n;u++)
     {
         for(i=head[u];i!=-1;i=edges[i].next)
         {
             v=edges[i].v;
             if(color[v]!=color[u])
             {
                 x=color[v];
                 y=color[u];
                 Add1(x,y);
                 deg[y]++;
             }
         }
     }
     while(!S.empty()) S.pop();
     for(i=1;i<=cnt;i++) if(!deg[i]) S.push(i);
     memset(p,0,sizeof(p));
     while(!S.empty())
     {
         u=S.top();
         S.pop();
         if(!p[u]) p[u]=1,p[col[u]]=-1;
         for(i=head1[u];i!=-1;i=edges1[i].next)
         {
             v=edges1[i].v;
             if(--deg[v]==0) S.push(v);
         }
     }
     memset(ans,0,sizeof(ans));
     for(i=0;i<n/2;i++)
     {
         if(p[color[i]]==p[color[0]]) ans[i]=1;
     }
 }
 
 int TWO_ST(int n)
 {
     int i;
 
     memset(dfn,0,sizeof(dfn));
     memset(visit,0,sizeof(visit));
     index=cnt=0;
     while(!S.empty()) S.pop();
     for(i=0;i<2*n;i++) if(!dfn[i]) Tarjan(i);
     for(i=0;i<n;i++)
     {
         if(color[i]==color[i+n]) return 0;
         col[color[i]]=color[i+n];
         col[color[i+n]]=color[i];
     }
     init(n);
     return 1;
 }
 
 void deal()
 {
     if(!TWO_ST(2*n))
     {
         puts("bad luck");
         return;
     }
     int i;
     for(i=1;i<n;i++)
     {
         if(ans[i]) printf("%dw",i);
         else printf("%dh",i);
         if(i<n-1) putchar(' ');
         else puts("");
     }
 }
 
 int main()
 {
     while(scanf("%d%d",&n,&m),n||m)
     {
         memset(head,-1,sizeof(head));
         e=0;
         int i,u,v;
         Add(2*n,0);
         Add(n,3*n);
         for(i=1;i<n;i++)
         {
             Add(i,i+3*n);
             Add(i+2*n,i+n);
             Add(i+n,i+2*n);
             Add(i+3*n,i);
         }
         char c1,c2;
         for(i=1;i<=m;i++)
         {
             scanf("%d%c%d%c",&u,&c1,&v,&c2);
             if(c1=='h') u+=n;
             if(c2=='h') v+=n;
             Add(u+2*n,v);
             Add(v+2*n,u);
         }
         deal();
     }
     return 0;
 }