比赛 |
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;
}