Cod sursa(job #2847938)

Utilizator SabailaCalinSabaila Calin SabailaCalin Data 11 februarie 2022 20:20:36
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <unordered_map>

using namespace std;

ifstream f ("dfs.in");
ofstream g ("dfs.out");

const int DIM = 100001;

int n, m;
int parent[DIM], rang[DIM];

int Find(int x)
{
    if (x != parent[x])
    {
        parent[x] = Find(parent[x]);
    }
    return x;
}

void Union(int x, int y)
{
    int rootX = Find(x);
    int rootY = Find(y);
    if (rootX != rootY)
    {
        if (rang[rootX] > rang[rootY])
        {
            parent[rootY] = rootX;
        }
        else
        {
            parent[rootX] = rootY;
            if (rang[rootX] == rang[rootY])
            {
                rang[rootY]++;
            }
        }
    }
}

void Read()
{
    f >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        Union(x, y);
    }
}

void Print()
{
    unordered_map <int, int> U_M;
    for (int i = 1; i <= n; i++)
    {
        U_M[Find(i)] = 1;
    }
    g << U_M.size();
}

int main()
{
    Read();
    Print();
}