yukicoder : No.2293 無向辺 2-SAT

これは割と典型かな…。
https://yukicoder.me/problems/no/2293

問題

N個の真偽値X[i]を格納する変数が与えられる。
これらに対する複数の条件をスタックで管理するものとする。
以下のクエリに順次答えよ。

• スタックに、2変数X[u],X[v]に対し{(X[u]=1)∨(X[v]=0)}∧{(X[u]=0)∨(X[v]=1)}という条件を加える。
• スタックに、2変数X[u],X[v]に対し{(X[u]=0)∨(X[v]=0)}∧{(X[u]=1)∨(X[v]=1)}という条件を加える。
• スタックを空にする

各クエリ毎に、条件を満たす変数の値の組み合わせが何通りかを答えよ。

解法

2N要素からなる無向グラフを考える。
各点は、X[i]=0の場合とX[i]=1の場合に相当し、点同士が連結である場合は、片方の変数がその値を取る場合、もう片方の変数が連結した頂点に対応する値を取らなければならないことを示す。
このグラフが奇閉路を持てば解はなし。(X[i]=0とX[i]=1を同時に満たすことはできないため)
奇閉路を持たない場合、2^(連結成分数/2)が解となる。
巻き戻し可能なUnion-Findを使い、連結成分数を数えていこう。

なお、2つの条件は、シンプルに言うとこうなる。

• X[u]==X[v]
• X[u]!=X[v]

template<int um> class UF_pop {
	public:
	vector<int> par,rank; vector<vector<int>> hist;
	UF_pop() {par=rank=vector<int>(um,0); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; hist.clear(); FOR(i,um) rank[i]=0,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):operator[](par[x]);}
	void pop() {
		if(hist.size()) {
			auto a=hist.back();
			hist.pop_back();
			par[a[0]]=a[1]; rank[a[0]]=a[2];
			par[a[3]]=a[4]; rank[a[3]]=a[5];
		}
	}
	void operator()(int x,int y) {
		x=operator[](x); y=operator[](y);
		hist.push_back({x,par[x],rank[x],y,par[y],rank[y]});
		if(x==y) return;
		if(rank[x]<rank[y]) par[x]=y;
		else rank[x]+=(rank[x]==rank[y]), par[y]=x;
	}
};

UF_pop<404040> uf;
const ll mo=998244353;
int p2[404040];
int N,Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	p2[0]=1;
	FOR(i,404010) p2[i+1]=p2[i]*2%mo;
	
	int num=2*N;
	int ng=0;
	while(Q--) {
		cin>>i;
		int U,V;
		if(i==1) {
			cin>>U>>V;
			U--,V--;
			if(uf[2*U]!=uf[2*V]) {
				num--;
				uf(2*U,2*V);
			}
			if(uf[2*U+1]!=uf[2*V+1]) {
				num--;
				uf(2*U+1,2*V+1);
			}
			if(uf[2*U]==uf[2*U+1]) ng=1;
			if(uf[2*V]==uf[2*V+1]) ng=1;
		}
		else if(i==2) {
			cin>>U>>V;
			U--,V--;
			if(uf[2*U]!=uf[2*V+1]) {
				num--;
				uf(2*U,2*V+1);
			}
			if(uf[2*U+1]!=uf[2*V]) {
				num--;
				uf(2*U+1,2*V);
			}
			if(uf[2*U]==uf[2*U+1]) ng=1;
			if(uf[2*V]==uf[2*V+1]) ng=1;
		}
		else {
			while(uf.hist.size()) uf.pop();
			num=2*N;
			ng=0;
		}
		
		if(ng) {
			cout<<0<<endl;
		}
		else {
			cout<<p2[num/2]<<endl;
		}
	}
}

まとめ

すんなり解けた。