"蔚来杯"2022牛客暑期多校训练营1 J Serval and Essay

本文主要是介绍"蔚来杯"2022牛客暑期多校训练营1 J Serval and Essay，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

启发式合并
对于任意入度为1的点，选择它的前驱进行染色一定优于对它本身染色，于是将这两点进行合并（_Merge部分）
合并的方向由两个点的出度决定，由出度小的点向出度大的点进行合并（这样最多只有n/2条要合并的边）
合并的过程中，可能会出现入度变为1的点，进行类似深搜的操作即可

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

#define fr first
#define se second
#define et0 exit(0);
#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef unsigned long long ULL;

const int INF = 0X3f3f3f3f, N = 2e5 + 10, MOD = 1e9 + 7;
const double eps = 1e-7;

int n;
int fa[N], sz[N];

set<int> from[N], to[N];

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void _Merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (to[x].size() < to[y].size()) swap(x, y);
	fa[y] = x, sz[x] += sz[y];

	vector<PII> mg;
	for (auto u : to[y]) {
		to[x].insert(u);
		from[u].erase(y);
		from[u].insert(x);
		if (from[u].size() == 1) mg.push_back({x, u});
	}

	for (auto u : mg)
		_Merge(u.fr, u.se);
}

void work() {
	cin >> n;
	rep(i, 1, n) from[i].clear(), to[i].clear();
	rep(i, 1, n) fa[i] = i, sz[i] = 1;
	rep(i, 1, n) {
		int k;
		cin >> k;
		rep(j, 1, k) {
			int y;
			cin >> y;
			from[i].insert(y);
			to[y].insert(i);
		}
	}
	rep(i, 1, n)
	if (from[i].size() == 1)
		_Merge(*from[i].begin(), i);
	int res = 0;
	rep(i, 1, n) res = max(res, sz[i]);
	cout << res << endl;
}

signed main() {
	int test = 1, tt = 1;
	cin >> test;

	while (test--) {
		printf("Case #%d: ", tt++);
		work();
	}

	return 0;
}

这篇关于"蔚来杯"2022牛客暑期多校训练营1 J Serval and Essay的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！