比赛 4043级NOIP2022欢乐赛5th 评测结果 AAAAAAAAAA
题目名称 遗传密码 最终得分 100
用户昵称 HeSn 运行时间 0.657 s
代码语言 C++ 内存使用 43.88 MiB
提交时间 2022-11-14 19:32:48
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
int n, m, inc[MAXN], out[MAXN], ans, vis[MAXN], flg, mp[MAXN];
vector<int> cd[MAXN];
void dfs(int x) {
//	cout << x << ' ';
	vis[x] = 1;
	if(inc[x] != out[x]) {
		flg = 0;
	}
	for(int i = 0; i < cd[x].size(); i ++) {
		int u = cd[x][i];
		if(vis[u]) {
			continue;
		}
		vis[u] = 1;
		dfs(u);
	}
}
signed main() {
	freopen("pie.in", "r", stdin);
	freopen("pie.out", "w", stdout);
	cin >> m;
	for(int i = 1; i <= m; i ++) {
		int x, y;
		cin >> x >> y;
		cd[x].push_back(y);
		cd[y].push_back(x);
		inc[y] ++;
		out[x] ++;
		mp[x] = 1;
		mp[y] = 1;
		n = max(n, x);
		n = max(n, y);
	}
	for(int i = 1; i <= n; i ++) {
		if(mp[i] && !vis[i]) {
			vis[i] = 1;
			flg = 1;
			dfs(i);
			ans += flg;
		}
	}
//	cout << ans << endl;
	for(int i = 1; i <= n; i ++) {
		if(mp[i] != 0) {
//			cout << ans << ' ';
			ans += max(inc[i], out[i]);
		}
	}
	cout << ans;
    return 0;
}