题解 ARC111B【Reversible Cards】

我们将值域中每个数视作一个节点，将每张卡片视作连接两个节点的边，则问题转化为：对于每条边都选择一个端点，使得被选择的节点总数最大。

显然每个连通块可以分开处理。设连通块的点数、边数为 \(v,e\)，可以证明这个连通块内被选择的节点总数为 \(\min\{v,e\}\)：

对于每个连通块，它要么是一棵树，要么有环（废话）。显然无论哪种情况，都不可能选超过 \(\min\{v,e\}\) 个节点。

对于一棵树，我们最多选 \(e\) 个节点：指定一个点当根，每条边都选更深的节点。

对于有环的图，我们最多选 \(v\) 个节点：找出一棵生成基环树，保证环上的每条边选择的节点都不同，然后指定环当根按照与树相同的策略就可以选到环外的所有节点。

洪水填充统计每个连通块的点数、边数即可。

// Problem: B - Reversible Cards
// Contest: AtCoder - AtCoder Regular Contest 111
// URL: https://atcoder.jp/contests/arc111/tasks/arc111_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
	uniform_int_distribution<int> dist(L, R);
	return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const int N = 4e5+5;

int n, vis[N], cntV, cntE, ans;
vector<int> e[N];

void dfs(int u) {
	vis[u] = 1;
	++cntV;
	for(int v : e[u]) {
		if(!vis[v]) dfs(v);
		++cntE;
	}
}

int main() {
	for(scanf("%d", &n); n; n--) {
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	rep(i, 1, N-1) {
		if(!vis[i]) {
			cntV = cntE = 0;
			dfs(i);
			cntE >>= 1;
			ans += min(cntV, cntE);
		}
	}
	printf("%d\n", ans);
	return 0;
}