Unionfind

マージテクUF

todoリストに載っていたので。 struct mergeUF { //O(logn^2) int n; vector<set<int>> g; vector<int> gat; void init(int mx) { n = mx; g.resize(n); gat.resize(n); rep(i, 0, n) { g[i].insert(i); gat[i] = i; } } mergeUF(int mx = 0) { init(mx); } void unite(int</int></set<int>…

2-SAT

(P||Q||...)&(R||S||...)みたいな連言標準形で書かれた論理式を真にする割り当てはあるかを判定する問題をSATといいます。 2-SATの場合カッコ内のリテラル数が高々2つ、つまり(P||Q)&(R||S)みたいになってます。2-SATの解き方は蟻本の通り、SCCを使って真のn…

AGC_016D: XOR Replace

http://agc016.contest.atcoder.jp/tasks/agc016_d うーん。Union Find見えてからが遅かった。EFもようわからん連結成分を考えれば良くて、変更前の数列のxorの値と変更後の数列のxorの値が等しいか異なるかで場合分け。 答えは(連結成分の数)+(異なる値の数…