额。。。我不能很好的解释这个算法，不过有一篇博客讲得挺好的，就是可能有点啰嗦。。。放在下面：
http://blog.csdn.net/moguxiaozhe/article/details/49047085
然后我一开始不会写，问副校长yf要了份代码，发现他写的好优美啊，果断学习了一波，这是我的代码，包括了o(n+m)的tarjan缩点+拓扑算法和o(nm)的暴力算法：
//o(n+m) #include<cstdio> #include<cstring> #include<queue> #include<vector> using namespace std; const int N=16010,M=40010; int n,m,mark[N]; struct E{int to,nxt;}; struct Graph { E e[M]; int head[N],cnt; void init(){memset(head,0,sizeof head);cnt=0;} void addedge(int x,int y){e[++cnt]=(E){y,head[x]};head[x]=cnt;} }; struct twosat { Graph G1,G2; int n,dfn[N],low[N],cnt,ind,in[N],s[N],top,col[N],bel[N],vis[N]; bool ins[N]; vector<int>vec[N]; void init(int n) { this->n=n; G1.init(); G2.init(); memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); memset(in,0,sizeof in); memset(col,0,sizeof col); for (int i=0;i<2*n;i++) vec[i].clear(); cnt=ind=0; } void add(int x,int y){G1.addedge(x,y^1); G1.addedge(y,x^1);} void tarjan(int u) { dfn[u]=low[u]=++ind; s[++top]=u; ins[u]=1; for (int i=G1.head[u];i;i=G1.e[i].nxt) { int v=G1.e[i].to; if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]); else if (ins[v]) low[u]=min(low[u],dfn[v]); } if (dfn[u]==low[u]) { while (1) { int x=s[top--]; bel[x]=cnt; vec[cnt].push_back(x); ins[x]=0; if (x==u) break; } cnt++; } } bool work() { for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i); for (int i=0;i<2*n;i+=2) if (bel[i]==bel[i^1]) return 0; queue<int>Q; for (int u=0;u<2*n;u++) for (int i=G1.head[u];i;i=G1.e[i].nxt) { int v=G1.e[i].to; if (bel[u]!=bel[v]) G2.addedge(bel[v],bel[u]),in[bel[u]]++; } for (int i=0;i<cnt;i++) if (!in[i]) Q.push(i); while (!Q.empty()) { int u=Q.front(); Q.pop(); if (!col[u]) { col[u]=1; for (int i=0;i<vec[u].size();i++) col[bel[vec[u][i]^1]]=2; } for (int i=G2.head[u];i;i=G2.e[i].nxt) { int v=G2.e[i].to; if (--in[v]==0) Q.push(v); } } for (int i=0;i<2*n;i++) mark[i]=col[bel[i]]; return 1; } }A; int read() {int d=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;} int main() { while (scanf("%d%d",&n,&m)!=EOF) { A.init(n); for (int i=1;i<=m;i++) A.add(read()-1,read()-1); if (!A.work()) {puts("NIE"); continue;} for (int i=0;i<2*n;i++) if (mark[i]==1) printf("%d ",i+1); } return 0; } //o(n*m) #include<cstdio> #include<cstring> const int N=160100,M=400000; struct edge{int to,nxt;}e[M<<1]; int n,m,head[N],cnt,s[N],top; bool b[N]; int read() {int d=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;} void addedge(int x,int y){e[++cnt]=(edge){y,head[x]}; head[x]=cnt;} bool dfs(int u) { if (b[u^1]) return 0; if (b[u]) return 1; b[u]=1; s[++top]=u; for (int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if (!dfs(v)) return 0; } return 1; } int main() { while (scanf("%d%d",&n,&m)!=EOF) { memset(head,0,sizeof head); memset(b,0,sizeof b); cnt=0; for (int i=1;i<=m;i++) { int x=read()-1,y=read()-1; addedge(x,y^1); addedge(y,x^1); } bool bo=1; for (int i=0;i<2*n;i+=2) if (!b[i]&&!b[i+1]) { top=0; if (!dfs(i)) { while (top) b[s[top--]]=0; if (!dfs(i+1)) {bo=0; break;} } } if (!bo) puts("NIE"); else for (int i=0;i<2*n;i++) if (b[i]) printf("%d ",i+1); } return 0; }
据周大神说这个o(nm)是假的，有大佬曾试图证明它是线形的，结果有一个可以卡成o(n^2)的数据，不过n^2还是很优秀的~
接下来做了些题，poj3207发现一直RE，原来是我边数组开小了。。。
#include<cstdio> #include<iostream> using namespace std; const int N=2017; struct E{int to,nxt;}e[N*N]; int n,m,a[N],b[N],dfn[N],low[N],ind,cnt,head[N],scc[N],s[N],top; bool ins[N]; void addedge(int x,int y) { e[++cnt]=(E){y,head[x]}; head[x]=cnt; e[++cnt]=(E){x,head[y]}; head[y]=cnt; } void tarjan(int u) { dfn[u]=low[u]=++ind; s[++top]=u; ins[u]=1; for (int i=head[u];i;i=e[i].nxt) { int v=e[i].to; if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]); else if (ins[v]) low[u]=min(low[u],dfn[v]); } if (dfn[u]==low[u]) { cnt++; while (1) { int x=s[top--]; ins[x]=0; scc[x]=cnt; if (x==u) break; } } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d",&a[i],&b[i]); if (a[i]>b[i]) swap(a[i],b[i]); } for (int i=1;i<=m;i++) for (int j=1;j<i;j++) if ((a[i]<a[j]&&b[i]>a[j]&&b[i]<b[j])||(a[i]>a[j]&&b[j]>a[i]&&b[i]>b[j])) { addedge(i<<1,j<<1|1); addedge(i<<1|1,j<<1); } cnt=0; for (int i=1;i<=m*2;i++) if (!dfn[i]) tarjan(i); for (int i=1;i<=m;i++) if (scc[i<<1]==scc[i<<1|1]) { puts("the evil panda is lying again"); return 0; } puts("panda is telling the truth..."); return 0; }
然后是bzoj1823，大概题意是至少选定a,b中的一个，这样我们只要连a'->b,b'->a，表示选了a'就必须选b，就好了。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<iostream> #include<string> #include<queue> #include<map> #include<set> #include<vector> #define mp make_pair #define pb push_back #define fi first #define se second #define sqr(x) (x)*(x) #define rep(i,x,y) for (int i=(x);i<=(y);i++) #define per(i,x,y) for (int i=(x);i>=(y);i--) using namespace std; typedef long long LL; typedef double DBD; typedef pair<int,int> pa; const int inf=1e9; const LL INF=1e18; //-----------------------------------------------head-------------------------------------------// const int N=211,M=2017; struct E{int to,nxt;}; struct Graph { E e[M<<1]; int cnt,head[N]; void init(){memset(head,0,sizeof head); cnt=0;} void addedge(int x,int y){e[++cnt]=(E){y,head[x]};head[x]=cnt;} }; struct twosat { Graph G1,G2; int n,dfn[N],low[N],ind,cnt,scc[N],s[N],top; bool ins[N]; void init(int n) { this->n=n; G1.init(); memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); ind=cnt=0; } void add(int x,int y){G1.addedge(x,y);} void tarjan(int u) { dfn[u]=low[u]=++ind; s[++top]=u; ins[u]=1; for (int i=G1.head[u];i;i=G1.e[i].nxt) { int v=G1.e[i].to; if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]); else if (ins[v]) low[u]=min(low[u],dfn[v]); } if (dfn[u]==low[u]) { cnt++; while (1) { int x=s[top--]; ins[x]=0; scc[x]=cnt; if (x==u) break; } } } bool work() { for (int i=2;i<=2*n+1;i++) if (!dfn[i]) tarjan(i); for (int i=2;i<=2*n+1;i+=2) if (scc[i]==scc[i+1]) return 0; return 1; } }A; int Write[20]; int n,m,T; char s1[3],s2[3]; int read() {int d=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;} void write(int x){int t=0; if (x<0) putchar('-'),x=-x; for (;x;x/=10) Write[++t]=x%10; if (!t) putchar('0'); for (int i=t;i>=1;i--) putchar((char)(Write[i]+48));} void judge(){freopen(".in","r",stdin); freopen(".out","w",stdout);} int main() { //judge(); T=read(); while (T--) { n=read(); m=read(); A.init(n); while (m--) { int b1,b2,x,y; char c=getchar(); while (c!='m'&&c!='h') c=getchar(); if (c=='m') b1=1; else b1=0; x=read(); c=getchar(); while (c!='m'&&c!='h') c=getchar(); if (c=='m') b2=1; else b2=0; y=read(); x<<=1; y<<=1; x+=b1; y+=b2; int xx=x,yy=y; if (b1) xx--; else xx++; if (b2) yy--; else yy++; A.add(xx,y); A.add(yy,x); //printf("%d %d %d %d ",xx,y,yy,x); } if (A.work()) puts("GOOD"); else puts("BAD"); } return 0; }
还在se题中，感觉2-sat的题主要还是转化模型。