【并查集+dfs】codeforces 1833 E. Round Dance

RomanLin / 2024-10-23 / 原文

题意

输入一个正整数 $T(1 \leq T \leq 10^4)$，表示接下来输入 $T$ 组测试用例，对于每一个测试用例：
第一行，输入一个正整数 $n(2 \leq n \leq 2 * 10^5)$
第二行，输入 $n$ 个正整数 $a_i(1 \leq a_i \leq n)$，表示节点 $i$ 到节点 $a_i$ 存在一条有向边，保证无自环

这 $n$ 个节点共同围成若干个环，特殊情况除只有两个节点的环以外，每个节点左右各有一个相邻节点。且每个环至少会有 $2$ 个节点。
问这 $n$ 个节点最少和最多各能组成多少个环？

题解

建立有向边后，必定可以划分为若干张（弱）连通图，连通图若整张图就是个环且节点数大于 $2$，则无法再插入更多元素，其他情况均可以与节点数大于等于3的环以外的（弱）连通图进行结合。

总结为：大二有环即为环，否则均为一条链

参考代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;

constexpr int N = 2e5 + 7;
int T = 1, n;
int a[N], in[N], dsu[N], sz[N];
bool vis[N];

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

void merge(int x, int y) { 
	int fx = find(x), fy = find(y);
	if (fx == fy) return ;
	dsu[fx] = fy; 
	sz[fy] += sz[fx];
}

void solve() {
	int cnt1 = 0, cnt2 = 0;
	cin >> n;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];	
		dsu[i] = i;
		sz[i] = 1;
		in[i] = 0;
		vis[i] = false;
	}
	auto dfs = [&](auto &&dfs, int x) -> void {
		vis[x] = true;
		in[a[x]] ++;
		merge(x, a[x]);
		if (!vis[a[x]]) dfs(dfs, a[x]);
	};
	unordered_map<int, bool> ump;
	for (int i = 1; i <= n; ++ i) if (!vis[i]) dfs(dfs, i);
	for (int i = 1; i <= n; ++ i) {
		bool b = in[i] == 2;
		int ro = find(i);
		if (ump.find(ro) == ump.end()) ump[ro] = b;
		else ump[ro] = b || ump[ro];
	}
	for (auto &it: ump) (it.second || sz[it.first] < 3 ? cnt1 : cnt2) ++;
	cout << cnt2 + (cnt1 > 0) << ' ' << cnt1 + cnt2 << '\n';
}

int main() {
	IOS
	cin >> T;
	while (T --) solve();
	return 0;
}