【題解】Zerojudge g598 - 4. 真假子圖

題目連結

題目大意

給定 $n$ 個點和 $m$ 條邊。現在有 $p$ 個調查員，每個調查員手中有 $k$ 條邊，我們稱一個調查員為間諜若且為若加入該調查員手中的 $k$ 條邊會使得圖變成不是二分圖。按照順序加入調查員的邊，問有哪些人是間諜？保證 $1 \leq \text{間諜的數量} \leq 3$。

題解

判斷二分圖可以用擴展域並查集去維護。假設我們要在圖中加入 $(u, v)$ 這條邊，相當於在並查集中合併 $(2u, 2v + 1)$ 和 $(2u + 1, 2v)$。假如在加入 $(u, v)$ 這條邊之前 $(2u, 2v)$ 在並查集中已經是同個集合的話加入後圖就不是二分圖。利用這個技巧我們可以 $O(1)$ 判斷當前狀態是否為二分圖。又因為題目保證間諜的數量 $\leq 3$，我們直接暴力加入每個調查員的邊，如果加入當前這個調查員的邊會變成不是二分圖，我們就直接砍掉重新蓋圖，只加入非間諜的邊。這樣暴力重新做的次數不會超過 $3$ 次，因此複雜度為 $O(m + pk)$。實作細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

struct dsu {
	int n;
	vector<int> sz;

	dsu() : n(0) {}
	explicit dsu(int _n) : n(_n), sz(_n, -1) {}

	int leader(int u) {
		return sz[u] < 0 ? u : (sz[u] = leader(sz[u]));
	}

	bool same(int u, int v) { return leader(u) == leader(v); }

	bool merge(int u, int v) {
		u = leader(u), v = leader(v);
		if(u == v) {
			return false;
		}
		if(-sz[u] < -sz[v]) {
			swap(u, v);
		}
		sz[u] += sz[v];
		sz[v] = u;
		return true;
	}
};

struct bipartite_checker {
	int n;
	dsu d;
	bool ok = true;

	bipartite_checker() : n(0) {}
	explicit bipartite_checker(int _n) : n(_n), d(2 * _n) {}

	void add_edge(int u, int v) {
		ok = ok && !d.same(2 * u, 2 * v);
		d.merge(2 * u, 2 * v + 1);
		d.merge(2 * u + 1, 2 * v);
	}

	bool is_bipartite() const { return ok; }
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	bipartite_checker b(n);
	vector<pair<int, int>> edges;
	edges.reserve(m);
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		b.add_edge(u, v);
		edges.emplace_back(u, v);
	}
	assert(b.is_bipartite());
	int p, k;
	cin >> p >> k;
	vector<vector<pair<int, int>>> pairs(p);
	for(int i = 0; i < p; i++) {
		pairs[i].reserve(k);
		for(int j = 0; j < k; j++) {
			int u, v;
			cin >> u >> v;
			pairs[i].emplace_back(u, v);
		}
	}
	vector<bool> bad(p);
	for(int i = 0; i < p; i++) {
		for(auto [u, v] : pairs[i]) {
			b.add_edge(u, v);
		}
		if(!b.is_bipartite()) {
			bad[i] = true;
			b = bipartite_checker(n);
			for(auto [u, v] : edges) {
				b.add_edge(u, v);
			}
			for(int j = 0; j < i; j++) {
				if(!bad[j]) {
					for(auto [u, v] : pairs[j]) {
						b.add_edge(u, v);
					}
				}
			}
		}
	}
	for(int i = 0; i < p; i++) {
		if(bad[i]) {
			cout << i + 1 << "\n";
		}
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge g598 - 4. 真假子圖