比赛 4043级NOIP2022欢乐赛5th 评测结果 AAAAAAAAAA
题目名称 遗传密码 最终得分 100
用户昵称 lihaoze 运行时间 0.183 s
代码语言 C++ 内存使用 2.30 MiB
提交时间 2022-11-14 20:02:01
显示代码纯文本
#include "bits/stdc++.h"

const int N = 1010;
int n;
int a[N], fa[N], ind[N], out[N];
std::set<int> s;

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

int main() {
    freopen("pie.in", "r", stdin); 
    freopen("pie.out", "w", stdout);
    std::cin >> n;

    for (int i = 1; i < N; ++ i) {
        fa[i] = i;
    }

    for (int i = 1; i <= n; ++ i) {
        int u, v;
        std::cin >> u >> v;

        ++ ind[v], ++ out[u];
        s.insert(u), s.insert(v);
        fa[find(u)] = find(v);
    }

    for (auto i : s) {
        if (ind[i] > out[i]) {
            a[find(i)] += ind[i] - out[i];
        }
    }

    int res = 0;
    for (auto i : s) {
        if (find(i) == i) {
            res += std::max(1, a[i]);
        }
    }
    res += n;

    std::cout << res << '\n';
    return 0;
}