Cod sursa(job #2260088)

Utilizator NewGloryMihnea Andreescu NewGlory Data 14 octombrie 2018 13:59:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <functional>
#include <iostream>

using namespace std;

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

int main()
{
    int n,m;
    fin>>n>>m;
    int ans=n;
    vector<int>h(n),t(n);
    for(int i=0;i<n;i++)
    {
        t[i]=i;
        h[i]=1;
    }
    function<int(int)>dad=[&](int a)
    {
        if(a==t[a]) return a;
        t[a]=dad(t[a]);
        return t[a];
    };
    function<void(int,int)>unite=[&](int a,int b)
    {
        a=dad(a);
        b=dad(b);
        if(a==b)
            return;
        ans--;
        if(h[a]<h[b])
        {
            t[a]=b;
        }
        else
        {
            t[b]=a;
            if(h[a]==h[b])
                h[a]++;
        }
    };
    while(m--)
    {
        int a,b;
        fin>>a>>b;
        a--;
        b--;
        unite(a,b);
    }
    fout<<ans<<"\n";
    return 0;
}