http://acm.hdu.edu.cn/showproblem.php?pid=1814
题意：n个2人组，编号分别为2n和2n+1，每个组选一个人出来，且给出m条关系（x,y）使得选了x就不能选y，问是否能从每个组选出1人。且输出字典序最小的答案。（n<=8000, m<=20000）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N=8005, M=20005;
struct E { int next, to; }e[M<<1];
int cnt, ihead[N<<1], top, s[N<<1], n, m;
bool vis[N<<1];
void add(int u, int v) { e[++cnt]=(E){ihead[u], v}; ihead[u]=cnt; }
bool dfs(int x) {
if(vis[x^1]) return 0;
if(vis[x]) return 1;
vis[x]=1;
s[++top]=x;
for(int i=ihead[x]; i; i=e[i].next) if(!dfs(e[i].to)) return 0;
return 1;
}
bool work() {
int nn=n<<1;
for(int i=0; i<nn; i+=2) if(!vis[i] && !vis[i+1]) {
top=0;
if(!dfs(i)) {
while(top) vis[s[top--]]=0;
if(!dfs(i+1)) return 0;
}
}
for(int i=0; i<nn; ++i) if(vis[i]) printf("%d\n", i+1);
return 1;
}
int main() {
while(~scanf("%d%d", &n, &m)) {
for(int i=0; i<m; ++i) { int x, y; scanf("%d%d", &x, &y); --x; --y; add(x, y^1); add(y, x^1); }
if(!work()) puts("NIE");
cnt=top=0;
memset(vis, 0, sizeof(bool)*(n<<1));
memset(ihead, 0, sizeof(int)*(n<<1));
}
return 0;
}
本题很显然的2-sat问题= =
对于关系（x,y）实际上就是满足!(x & y)
即当x=1时y必须为0，即连边x->y'
当y=1时x必须为1，即连边y->x'
由于这个dfs的算法本身就是字典序最小了= =直接搞就行了= =
（妈呀难道这个算法是O(nm)的嘛QAQ看来得写tarjan了以后= =（虽然字典序最小只能用这个O(nm)算法= =？）
