http://poj.org/problem?id=3648
题意：n对人（编号0～n-1，'w'表示第一个人，'h'表示第二个人），每对两个，人坐在桌子两侧。满足：1、每对人中的两个人不能坐在同一侧。2、m对关系x和y，表示x和y不能坐在同一侧，但是能坐在第0对的第一个人的那一侧。问第0对的第一个人那一侧坐着的人。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N=1005;
int tot, FF[N], LL[N], p[N], in[N], num, all, top, ok[N], vis[N], pos[N], n, m;
struct Gr {
int ihead[N], cnt;
struct E{ int next, to; }e[N*N<<2];
Gr() { cnt=0; memset(ihead, 0, sizeof ihead); }
void add(int u, int v) { e[++cnt]=(E){ihead[u], v}; ihead[u]=cnt; }
void tarjan(int x) {
static int s[N];
FF[x]=LL[x]=++tot; vis[x]=1; s[++top]=x;
for(int i=ihead[x]; i; i=e[i].next)
if(!FF[e[i].to]) tarjan(e[i].to), LL[x]=min(LL[x], LL[e[i].to]);
else if(vis[e[i].to]) LL[x]=min(LL[x], FF[e[i].to]);
if(FF[x]==LL[x]) {
int y; ++num;
do { y=s[top--]; vis[y]=0; p[y]=num; } while(x!=y);
}
}
void tarjan() { tot=0; top=0; num=0; for(int i=0; i<all; ++i) if(!FF[i]) tarjan(i); }
void rebuild(Gr &g) {
for(int x=0; x<all; ++x)
for(int i=ihead[x]; i; i=e[i].next) if(p[x]!=p[e[i].to])
in[p[x]]++, g.add(p[e[i].to], p[x]);
for(int x=0; x<all; x+=2) pos[p[x]]=p[x|1], pos[p[x|1]]=p[x];
}
void topo() {
static int q[N], front, tail; front=tail=0;
for(int i=0; i<num; ++i) if(!in[i]) q[tail++]=i;
while(front!=tail) {
int x=q[front++];
if(!ok[x]) ok[x]=1, ok[pos[x]]=2;
for(int i=ihead[x]; i; i=e[i].next) if(!(--in[e[i].to])) q[tail++]=e[i].to;
}
}
void clr() {
memset(ihead, 0, sizeof(int)*(all));
cnt=0;
}
}g, G;
void clr() {
memset(FF, 0, sizeof(int)*(all));
memset(in, 0, sizeof(int)*(all));
memset(ok, 0, sizeof(int)*(all));
memset(p, 0, sizeof(int)*(all));
memset(pos, 0, sizeof(int)*(all));
G.clr(); g.clr();
all=0;
}
bool work() {
all=n<<1;
g.tarjan();
for(int i=0; i<all; i+=2) if(p[i]==p[i+1]) return 0;
g.rebuild(G);
G.topo();
int white=ok[p[0]]; // printf("%d
", white);
for(int i=1; i<n-1; ++i) printf("%d%c ", i, white==ok[p[i<<1]]?'w':'h');
printf("%d%c
", n-1, white==ok[p[(n-1)<<1]]?'w':'h');
return 1;
}
int main() {
while(scanf("%d%d", &n, &m), !(n==0&&m==0)) {
for(int i=0; i<m; ++i) {
static char s1, s2;
int x, y;
scanf("%d%c%d%c", &x, &s1, &y, &s2);
int a=x<<1|(s1=='h'),
b=y<<1|(s2=='h');
g.add(a, b^1); g.add(b, a^1);
}
g.add(0, 1);
if(!work()) puts("bad luck");
clr();
}
return 0;
}
一开始写的好几个都给wa了= =因为感觉整个题我写得都有问题，所以一怒之下我删了！然后看别人家的代码= =（但是后来发现本题有一个坑，就是读入的时候可能没有空格，因此不能读入"%s%s"= =，会不会这样就能a掉了呢= =）
这题我做得很郁闷= =各种不想说了..
大家请转移阵地（请结合三份题解一起看= =感觉各有缺漏= =）= =http://www.cnblogs.com/staginner/archive/2011/10/02/2198263.html，http://www.cnblogs.com/kuangbin/archive/2012/10/05/2712429.html，http://blog.csdn.net/qq172108805/article/details/7603351
（这里我不得不说一下= =状态设的是第0对第一个人的“对面”= =大家千万不要搞错了= =
那么 x -> y'的意思表示x坐在对面那么y'一定也坐在对面
最后0w -> 0h表示0对人只有h人坐在对面。