1209D - Cow and Snacks - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define si short int
#define ll long long int
#define ull unsigned long long int
#define mod 1000000007
#define endl "\n"
#define space " "
#define debug(argument) cout << "debug_point: " << argument << endl;
#define printvectorset(vs)      \
    for (auto &value : vs)      \
    {                           \
        cout << value << space; \
    }                           \
    cout << endl;
///////////////////////// Garvit_Goyal /////////////////////////////
int find_parent(int u, vector<int> &parent)
{
    if (parent[u] == u)
    {
        return u;
    }
    return parent[u] = find_parent(parent[u], parent);
}

void make_union(int u, int v, vector<int> &parent, vector<int> &size)
{
    u = find_parent(u, parent);
    v = find_parent(v, parent);
    if (u == v)
    {
        return;
    }
    if (size[u] < size[v])
    {
        swap(u, v);
    }
    parent[v] = u;
    size[u] += size[v];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    /* #ifndef ONLINE_JUDGE
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
     #endif*/
    int n, k;
    cin >> n >> k;

    vector<int> parent(n + 1);
    vector<int> size(n + 1, 1);
    vector<si> flagVector(n + 1, 0);
    map<int, int> childCnt;

    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
    }
    for (int i = 0; i < k; i++)
    {
        int u, v;
        cin >> u >> v;
        make_union(u, v, parent, size);
        childCnt[u]++;
        childCnt[v]++;
    }

    for (auto &value : childCnt)
    {
        if (value.second == 1)
        {
            flagVector[find_parent(value.first, parent)] += 1;
        }
    }

    int satisfied = 0;
    for (int i = 1; i <= n; i++)
    {
        if (parent[i] == i)
        {
            // cout << "adding " << size[i] - 1 << " at " << i << endl;
            satisfied += (size[i] - 1);
        }
    }
    // debug(satisfied);
    if (satisfied < n)
    {
        cout << k - satisfied << endl;
    }
    else
    {
        cout << 0 << endl;
    }
    return 0;
}