Cod sursa(job #3344129)

Utilizator mirceav23Grecea Mircea mirceav23 Data 1 martie 2026 13:54:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define eb emplace_back
#define cin fin
#define cout fout
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int t[100020], r[100020];

void unire(int x, int y)
{
if (r[x]>r[y])
    t[y]=x;
else
    {
    if  (r[x]<r[y])
        t[x]=y;
    else
        {
        t[y]=x;
        r[x]++;
        }
    }
}

int findu(int x)
{
int temp, rad;
rad=x;

while (t[rad]!=0)
    rad=t[rad];
while (t[x]!=0)
    {
    temp=t[x];
    t[x]=rad;
    x=temp;
    }
return rad;
}

int n, m, x, y, c, nr;
int r1, r2;

int main()
{
    cin>>n>>m;
    vector<vector<int>> comp(n+1);
    nr=n;

    for (int i=1; i<=n; i++)
        comp[i].eb(i);

    for (int i=1; i<=m; i++)
        {
        cin>>x>>y;
        r1=findu(x);
        r2=findu(y);
        if (r1!=r2)
            {
            if (r[r1]>=r[r2])
                {
                for (auto i:comp[y])
                    comp[r1].eb(i);
                comp[y].clear();
                unire(r1, r2);
                nr--;
                }
            else
                {
                for (auto i:comp[x])
                    comp[r2].eb(i);
                comp[x].clear();
                unire(r1, r2);
                nr--;
                }
            }
        }
    cout<<nr;
}