题意

有N个点，M条边的无向图，有些边是0，有些边是1，现在给定一个操作：选择一个点，把其相连接点边的0/1状态取反，问最多N次操作，可不可能把所有边都变成1？如果可以，输出方案

解法

对于一个点，要么操作0次，要么操作1次，因为取反再取反就等于没有取反。
所以对于边为1的两个端点，x和y要么都操作，要么都不操作，x，y异或为0
对于边为0的两个端点，要么x操作，y不操作，要么y操作，x不操作，x，y异或为1
建立边之后，就跑一下2-sat即可

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}


//--------------------------------------------
int N,M;
int h[maxn],e[maxn],ne[maxn],idx = 1;
int dfn[maxn],low[maxn],scc_id[maxn],scc,tim;
int sk[maxn],top; bool in_sk[maxn];

void add(int a,int b){
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}
int opp(int x){
    if(x <= N) return x + N;
    else return x - N;
}
void tarjan(int u){
    dfn[u] = low[u] = ++ tim;
    sk[++top] = u; in_sk[u] = 1;
    for(int i = h[u];i;i = ne[i]){
        int v = e[i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }else if(in_sk[v]){
            low[u] = min(low[u],dfn[v]); 
        }
    }
    if(dfn[u] == low[u]){
        ++scc;
        int v;
        do{
            v = sk[top--];in_sk[v] = 0;
            scc_id[v] = scc;
        }while(v != u);
    }
}
void solve(){
    for(int i = 1;i<=2*N;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    bool ok = 1;
    for(int i = 1;i<=N;i++){
        if(scc_id[i] == scc_id[opp(i)]){
            ok = 0;
            break;
        }
    }
    if(!ok) puts("Impossible");
    else{
        int cnt = 0;
        for(int i = 1;i<=N;i++){
            if(scc_id[i] < scc_id[opp(i)]){
                cnt++;
            }
        }
        cout<<cnt<<'\n';
        int tag = 1;
        for(int i = 1;i<=N;i++){
            if(scc_id[i] < scc_id[opp(i)]){
                if(tag) tag = 0;else putchar(' ');
                printf("%d",i);
            }
        }
    }
}
int main(){
    // debug_in;

    read(N,M);
    for(int i = 1;i<=M;i++){
        int x,y,t;read(x,y,t);
        if(t == 0){
            add(x,opp(y));
            add(opp(x),y);
            add(y,opp(x));
            add(opp(y),x);
        }else{
            add(x,y);
            add(y,x);
            add(opp(x),opp(y));
            add(opp(y),opp(x));
        }
    }
    solve();

    return 0;
}

E. The Road to Berland is Paved 【2-sat】1900

题意

解法