POJ_3648
首先要注意两个和算法无关地方：①题目的输入数据存在诸如“2w5h”的情况，因此直接用scanf(“%s%s”,b1,b2)去读取数据会WA。②题目中的意思是找出一组能和新娘坐在一起的人，而题目中描述的对于人的限制都是指的对面的，因此我们要先利用已知把对面的人的序列构造出来，再输出对应的新娘这边的人的序列即可。
这是我的第一个2-SAT的题目，做完一题相当于复习了好多图论的知识……总的来说，这类问题一般的步骤是这个样子的：
①根据已知条件建图。比如这一题，已知的条件是x和y不能同时坐在对面（注意，与不能同时坐在一起是不同的），那么我们就要连两条边，x->~y，y->~x，至于为什么这么建图，主要是从意义上考虑的，x和y不能同时坐在对面，也就是说如果坐了x，那么对面就只能做~y，反过来也是一样的，所以x->~y与~y->x不是等价的。如果我们设新娘是0，新郎是1的话，同时需要连一条0->1的边，表示对面只能坐新郎，因为如果0坐在对面，那么1也要坐在对面，显然不符合逻辑。
②用tarjan算法（当然别的算法也可以，只不过我只会tarjan）求强连通分量。至于为什么有这一步，可以参考PPT《由对称性解2-SAT问题》。
③判断每个集合中的两个元素是否在同一个强连通分量中。如果存在一个集合中的两个元素在同一个强连通分量中，则无解，否则一定有解（至于为什么一定有解，可以参考PPT《由对称性解2-SAT问题》）。
④依原来的有向边，将缩后的点构造成反向图并进行拓扑排序（便于后续的处理）。
⑤删点并记录方案。这个过程需要一个数组del[]表示缩后的点是否被删去，然后依次遍历每个强连通分量，如果del[]不为1，则把强连通分量里的值全部取出，在取出的x的同时，删除~x所在的强连通分量以及该强连通分量的所有直接或间接的子节点。这样的做的目的可以这么来理解，如果我们选择了x，那么就不能选~x，所以凡是选了y就必须选~x的y都要被删去，又因为我们建的是反图，所以要删掉所有~x所在的强连通分量以及该强连通分量的所有直接或间接的子节点。
⑥打印结果。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n, m, N, G[1010][1010];
int col , a[1010][1010], num[1010], color[1010];
int g[1010][1010], dfn[1010], low[1010];
int s[1010], top, time, ins[1010];
int topo[1010], t, del[1010], vis[1010];
int ans[1010], res;
int cmp(const void *_p,const void *_q)
{
int *p=(int *)_p;
int *q=(int *)_q;
return *p-*q;
}
int init()
{
int i, j, k, n1, n2;
char b1,b2;
scanf("%d%d", &n, &m);
if(!n&&!m)
return 0;
N = 2 * n;
memset(G, 0, sizeof(G));
for(i = 0; i < m; i ++)
{
scanf("%d%c%d%c", &n1, &b1, &n2, &b2);
n1 = n1 * 2 + (b1 == 'h');
n2 = n2 * 2 + (b2 == 'h');
G[n1][n2 ^ 1] = 1;
G[n2][n1 ^ 1] = 1;
}
G[0][1] = 1;
return 1;
}
void tarjan(int u)
{
int i, j, v;
dfn[u] = low[u] = ++time;
for(v = 0; v < N; v ++)
if(G[u][v])
{
if(!dfn[v])
{
s[top ++] = v;
ins[v] = 1;
tarjan(v);
if(low[v] < low[u])
low[u] = low[v];
}
else if(ins[v] && dfn[v] < low[u])
low[u] = dfn[v];
}
if(low[u] == dfn[u])
{
for(i = 0, s[top] = -1; s[top] != u; i++)
{
top --;
a[col][i] = s[top];
color[s[top]] = col;
ins[s[top]] = 0;
}
num[col] = i;
col ++;
}
}
int judge()
{
int i;
for(i = 0;i < N; i ++)
if(color[i] == color[i ^ 1])
return 0;
return 1;
}
int dfs(int u)
{
int i, j, v;
vis[u] = -1;
for(v = 0; v < col; v ++)
if(g[u][v])
{
if(vis[v] == -1)
return 0;
if(!vis[v] && !dfs(v))
return 0;
}
vis[u] = 1;
topo[-- t] = u;
return 1;
}
int toposort()
{
int i, j, k;
t = col;
memset(vis, 0, sizeof(vis));
for(i = 0; i < col; i ++)
if(!vis[i] && !dfs(i))
return 0;
return 1;
}
void dfsdel(int u)
{
int v;
del[u] = 1;
for(v = 0; v < col; v ++)
if(g[u][v] && !del[v])
dfsdel(v);
}
void search(int i)
{
int j, p;
del[i] = 1;
for(j = 0; j < num[i]; j ++)
{
p = a[i][j];
ans[res ++] = p;
if(!del[color[p ^ 1]])
dfsdel(color[p ^ 1]);
}
}
int com()
{
int i, j, k, p, ok;
top = time = col = 0;
memset(ins, 0, sizeof(ins));
memset(dfn, 0, sizeof(dfn));
for(i = 0; i < N; i ++)
if(! dfn[i])
{
s[top ++] = i;
ins[i] = 1;
tarjan(i);
}
if(!judge())
return 0;
memset(g, 0, sizeof(g));
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(G[i][j] && color[i] != color[j])
g[color[j]][color[i]] = 1;
if(!toposort())
return 0;
memset(del , 0, sizeof(del));
res = 0;
for(i = 0; i < col; i ++)
if(!del[topo[i]])
search(topo[i]);
if(res != n)
return 0;
return 1;
}
void printpath()
{
int i, j, tt;
tt = 0;
qsort(ans, res, sizeof(ans[0]), cmp);
for(i = 1; i < res; i ++)
{
if(tt ++)
printf(" ");
printf("%d%c", ans[i] / 2, ans[i] % 2 == 0 ? 'h' : 'w');
}
printf("\n");
}
int main()
{
while(init())
{
if(com())
printpath();
else
printf("bad luck\n");
}
return 0;
}