hdu1814 Peaceful Commission

链接

emm，三个链接，三个都不同
loj随便做
hdu字典序最小
bzoj求合法方案数

思路

loj是任意一组解，直接跑tarjan然后判。
hdu是求最小字典序的2-sat解，真的是码力弱的要死呀。
只有O(N*M)的dfs复杂度能做。
如果不会2-sat的看这里

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s<='9'&&s>='0';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m;
struct node {
    int v,nxt;
}e[N];
int head[N],tot;
void add(int u,int v) {
//  cout<<u<<" "<<v<<"\n";
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int stak[N],top,vis[N];
bool dfs(int u) {
    if(vis[u]) return 1;
    if(vis[u^1]) return 0;
    vis[u]=1;
    stak[++top]=u;
    for(int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if(!dfs(v)) return 0;
    }
    return 1;
}
void clear() {
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
    tot=0;
}
int main() {
//  freopen("a.in","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF) {
        clear();
        for(int i=1;i<=m;++i) {
            int x=read()-1,y=read()-1;
            add(x,y^1);
            add(y,x^1);
        }
        int flag=0;
        for(int i=0;i<n+n;i+=2) {
            if(!vis[i]&&!vis[i+1]) {
                top=0;
                if(!dfs(i)) {
                    while(top) vis[stak[top--]]=0;
                    if(!dfs(i+1)) {flag=1;break;}
                }
            }
        }
        if(flag) puts("NIE");
        else {
            for(int i=0;i<n+n;++i)
                if(vis[i]) printf("%d\n",i+1);
        }
    }   
    return 0;
}