Submission

Score: 23

User: Xapitize

Problemset: Tech Sprites

Language: cpp

Time: 0.579 second

Submitted On: 2026-03-20 18:47:21

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) (x).begin(), (x).end()

vector<pair<int,int>> spirits(1e6+2); // shy , spark
vector<int> parent(1e6+2);

int findRoot(int u)
{
    if(parent[u]==u) return u;
    return parent[u] = findRoot(parent[u]);
}

void uni(int u, int v)
{
    if(findRoot(u) != findRoot(v))
    {
        parent[findRoot(u)] = parent[findRoot(v)];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin >> a >> b;
        spirits[i] = {a,b};
    }
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
    }
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin >> x >> y;
        uni(x,y);
    }
    set<int> subgroup;
    for(int i=1;i<=n;i++)
    {
        subgroup.insert(findRoot(i));
    }
    cout << subgroup.size()-1;
    return 0;
}