Cod sursa(job #3306476)

Utilizator lucazguroiuLuca Zguroiu lucazguroiu Data 10 august 2025 21:31:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;
string filename = "dfs";
ifstream in(filename + ".in");
ofstream out(filename + ".out");

vector<int> r, parent;

int findParent(int node)
{
    if(parent[node] == node)
        return node;
    return parent[node] = findParent(parent[node]);
}
int conex;
void unite(int a, int b)
{
    int parA = findParent(a);
    int parB = findParent(b);
    if(parA==parB)
        return;
    if(r[parA] < r[parB])
        parent[parA] = parB;
    else if (r[parB] < r[parA])
        parent[parB] = parA;
    else
        parent[parB] = parA,
        r[parA]++;
    conex--;
}
int n, m;
int main()
{
    in>>n>>m;
    r.resize(n+1,0);
    parent.resize(n+1);
    for(int i = 0; i<=n;i++)
        parent[i]=i;
    conex=n;
    int a,b;
    for(int i = 1; i<=m ;i++)
    {
        in>>a>>b;
        unite(a,b);
    }
    out<<conex;

    return 0;
}