Klee and Bomb

The first line of input contains two integers $n(1\le n\le 3\times 10^5)$ and $m(0\le m\le 3\times 10^5)$ --- the number of bombs and links respectively.
The second line contains $n$ integers $c_1, c_2, \dots, c_n(1\le c_i\le n)$ --- the color of each bomb.
In the next $m$ lines, each line contains two integers $u, v(1\le u,v\le n, u\ne v)$ --- two bombs which is connected by the link.
It is guaranteed that for any pair of bombs $(x, y)$ , there are at most $1$ link between them.

C++ 解法, 执行用时: 236ms, 内存消耗: 22312K, 提交时间: 2021-12-18 14:53:43

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr LL mod = 998244353;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<int> c(n + 1), p(n + 1, -1);
	for (int i = 1; i <= n; i += 1)
		cin >> c[i];
	function<int(int)> fp = [&](int u) {
		return p[u] < 0 ? u : p[u] = fp(p[u]);
	};
	vector<vector<int>> G(n + 1);
	int ans = 1;
	for (int i = 0, u, v; i < m; i += 1) {
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
		if (c[u] == c[v]) {
			int pu = fp(u), pv = fp(v);
			if (pu != pv) {
				p[pv] += p[pu];
				p[pu] = pv;
				ans = max(ans, -p[pv]);
			}
		}
	}
	for (int i = 1; i <= n; i += 1) {
		set<int> s;
		map<int, int> mp;
		for (int v : G[i]) if (c[v] != c[i]) {
			if (not s.count(fp(v))) {
				s.insert(fp(v));
				mp[c[v]] += -p[fp(v)];
			}
		}
		for (auto [x, y] : mp) ans = max(ans, y + 1);
	}
	cout << ans;
	return 0;
}

详情