Submission #869387

#	Time	Username	Problem	Language	Result	Execution time	Memory
869387		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	1 ms	2136 KiB

commuter_pass

#include <iostream>
#include <cstdint>

using namespace std;

constexpr int64_t maxn = 100000;
int64_t n, m, c;
int64_t parent[maxn + 1];

int64_t GetSet(int64_t v)
{
    if (parent[v] == v)
        return v;

    return parent[v] = GetSet(parent[v]);
}

void Union(int64_t v, int64_t u)
{
    if (v != u)
        c--;

    parent[v] = u;
}

int main()
{
    cin >> n >> m;

    c = n;
    for (int64_t i = 1; i <= n; i++)
        parent[i] = i;

    for (int64_t i = 1; i <= m; i++)
    {
        int64_t v, u;
        cin >> v >> u;
        Union(GetSet(v), GetSet(u));
    }

    cout << m - n + c << '\n';

    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45