"蔚来杯"2022牛客暑期多校训练营1 - J. Serval and Essay题解 (启发式合并+set)

Serval and Essay

原题指路:https://ac.nowcoder.com/acm/contest/33186/J

题意 ($2\mathrm{s}2\backslash \; \backslash mathrm\{s\}$)

给定一张包含$nn$个节点$mm$条边的无重边无自环的有向图,初始时每个节点都为白色.现可将一个节点染黑,若一个节点的所有入边的起点都为黑色,则该节点可被染黑,求最终图中黑色节点数的最大值.

有$t(1\le t\le 1\mathrm{e}5)t\backslash \; \backslash \; (1\backslash leq\; t\backslash leq\; 1\backslash mathrm\{e\}5)$组测试数据.每组测试数据第一行输入一个$n(1\le n\le 2\mathrm{e}5)n\backslash \; \backslash \; (1\backslash leq\; n\backslash leq\; 2\backslash mathrm\{e\}5)$,表示节点数.接下来$nn$行每行先输入一个整数,接下来输入$kk$个整数$a_{i,1},a_{i,2},\cdots ,a_{i,k_i}(1\le a_{i,j}\le n,a_{i,j}\mathrm{\ne }i)a\_\{i,1\},a\_\{i,2\},\backslash cdots,a\_\{i,k\_i\}\backslash \; \backslash \; (1\backslash leq\; a\_\{i,j\}\backslash leq\; n,a\_\{i,j\}\backslash neq\; i)$,分别表示节点$ii$的前驱节点的编号.数据保证对$\mathrm{\forall }i\in [1,n]\backslash forall\; i\backslash in[1,n]$,当$j\mathrm{\ne }kj\backslash neq\; k$时,有$a_{i,j}\mathrm{\ne }{a}_{i,k}a\_\{i,j\}\backslash neq\; a\_\{i,k\}$.数据保证所有测试数据的$nn$之和不超过$2\mathrm{e}52\backslash mathrm\{e\}5$,所有$k_{i}k\_i$之和不超过$5\mathrm{e}55\backslash mathrm\{e\}5$.

对每组测试数据,输出"Case #i: x",其中$ii$为测试数据的编号(从$11$开始),$xx$为最终图中黑色节点数的最大值.

思路

注意到当一个节点入度为$11$时,只需将其前驱节点染黑,则该节点及其前驱节点都为黑色,且此时两节点等价为一个点,此过程可用并查集维护.注意合并两节点时需合并两节点所连的边.特别地,若存在有向边和,则合并节点$uu$和$vv$时,应将节点$ss$的入度$-1-1$,去重和删除可用set维护.

用启发式合并优化合并过程,时间复杂度$O(m\log m)O(m\backslash log\; m)$.set的时间复杂度为$O(\log m)O(\backslash log\; m)$,总时间复杂度$O(m{}^{2}m)O(m\backslash log^2\; m)$,最坏约$1.8\mathrm{e}81.8\backslash mathrm\{e\}8$,可过.

代码I : DFS写法 (参考 : ThreePigs)

const int MAXN = 2e5 + 5;
int n;  // 节点数
int fa[MAXN];  // 并查集的fa[]数组
int siz[MAXN];  // 每个集合的大小
set<int> nxt[MAXN], pre[MAXN];  // 有向边中节点的后继和前驱

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

void merge(int u, int v) {  // 合并节点x和节点y所在的集合
	u = find(u), v = find(v);
	if (u == v) return;  // 已在同一集合中

	if (nxt[u].size() < nxt[v].size()) swap(u, v);  // 保证将v的集合合并到x的集合
	fa[v] = u, siz[u] += siz[v];

	vii tmp;  // 待更新的节点
	for (auto t : nxt[v]) {  // 枚举节点v的所有出边v->t
		pre[t].erase(v), pre[t].insert(u);  // 删去v->t,改为u->t
		nxt[u].insert(t);  // 连有向边u->t

		if (pre[t].size() == 1) tmp.push_back({ t,u });  // 入度减为1的节点入队
	}

	for (auto [x, y] : tmp) merge(x, y);
}

void solve() {
	int T; cin >> T;
	for (int C = 1; C <= T; C++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			fa[i] = i, siz[i] = 1;
			nxt[i].clear(), pre[i].clear();
		}

		for (int v = 1; v <= n; v++) {  // 有向边u->v
			int k; cin >> k;
			while (k--) {
				int u; cin >> u;
				nxt[u].insert(v), pre[v].insert(u);
			}
		}
		
		for (int i = 1; i <= n; i++)  // 从入度为1的节点开始DFS
			if (pre[i].size() == 1) merge(*pre[i].begin(), i);

		int ans = 0;
		for (int i = 1; i <= n; i++) ans = max(ans, siz[i]);
		cout << "Case #" << C << ": " << ans << endl;
	}
}

int main() {
	solve();
}

代码II : BFS写法

const int MAXN = 2e5 + 5;
int n;  // 节点数
int fa[MAXN];  // 并查集的fa[]数组
int siz[MAXN];  // 每个集合的大小
set<int> nxt[MAXN], pre[MAXN];  // 有向边中节点的后继和前驱

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

void bfs() {
	deque<pii> que;
	for (int i = 1; i <= n; i++)  // 入度为1的节点入队
		if (pre[i].size() == 1) que.push_back({ *pre[i].begin(),i });

	while (que.size()) {
		auto [u, v] = que.front(); que.pop_front();
		u = find(u), v = find(v);
		if (u == v) continue;  // 已在同一集合中

		if (nxt[u].size() < nxt[v].size()) swap(u, v);  // 保证将v的集合合并到x的集合
		fa[v] = u, siz[u] += siz[v];

		for (auto t : nxt[v]) {  // 枚举节点v的所有出边v->t
			pre[t].erase(v), pre[t].insert(u);  // 删去v->t,改为u->t
			nxt[u].insert(t);  // 连有向边u->t

			if (pre[t].size() == 1) 
				que.push_front({ t,u });  // 入度减为1的节点入队,应优先更新,故插到队首
		}
	}
}

void solve() {
	int T; cin >> T;
	for (int C = 1; C <= T; C++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			fa[i] = i, siz[i] = 1;
			nxt[i].clear(), pre[i].clear();
		}

		for (int v = 1; v <= n; v++) {  // 有向边u->v
			int k; cin >> k;
			while (k--) {
				int u; cin >> u;
				nxt[u].insert(v), pre[v].insert(u);
			}
		}
		
		bfs();

		int ans = 0;
		for (int i = 1; i <= n; i++) ans = max(ans, siz[i]);
		cout << "Case #" << C << ": " << ans << endl;
	}
}

int main() {
	solve();
}