hdu1814 Peaceful Commission

链接

emm，三个链接，三个都不同

随便做

字典序最小

求合法方案数

思路

loj是任意一组解，直接跑tarjan然后判。

hdu是求最小字典序的2-sat解，真的是码力弱的要死呀。

只有O(N*M)的dfs复杂度能做。

如果不会2-sat的看

代码

#include 
    
     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<
     <<" "<
      
       <<"\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