Cod sursa(job #2911334)

Utilizator GligarEsterabadeyan Hadi Gligar Data 28 iunie 2022 16:15:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
#include <fstream>

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

class array{
private:
    int *p;
    int n,c;
    void double_size();
public:
    array();
    array(int x, int y);
    ~array();
    int get_size();
    void set_size(int num);
    void set_size(int num, int val);
    void push_back(int x);
    void pop_back();
    void shrink();
    void operator =(array &other);
    int& operator [](int x);
};


array::array(){
    p=nullptr;
    n=0;
    c=0;
}

array::array(int x, int y){
    p=new int[x];
    n=x;
    c=x;
}

array::~array(){
    delete[] p;
}

void array::double_size(){
    if(c!=0){
        int *q=new int[c*2];
        for(int i=0;i<n;i++){
            q[i]=p[i];
        }
        delete[] p;
        p=q;
        c*=2;
    }else{
        c=1;
        p=new int[c];
    }
}

int array::get_size(){
    return n;
}

void array::set_size(int x){
    if(x<=c){
        n=x;
    }else if(x<=c*2){
        double_size();
        n=x;
    }else{
        int *q=new int[x];
        for(int i=0;i<n;i++){
            q[i]=p[i];
        }
        delete[] p;
        p=q;
        c=x;
        n=x;
    }
}

void array::set_size(int x, int y){
    int oldn=n;
    set_size(x);
    for(int i=oldn;i<x;i++){
        p[i]=y;
    }
}

void array::push_back(int x){
    if(n==c){
        double_size();
    }
    p[n]=x;
    n++;
}

void array::pop_back(){
    n--;
}

void array::shrink(){
    if(c!=n){
        int *q=new int[n];
        for(int i=0;i<n;i++){
            q[i]=p[i];
        }
        delete[] p;
        p=q;
        c=n;
    }
}

void array::operator=(array &other){
    set_size(other.n);
    for(int i=0;i<n;i++){
        p[i]=other[i];
    }
}

int& array::operator[](int x){
    return p[x];
}

const int nmax=100000;

array g[nmax+1];

bool u[nmax+1];

void dfs(int x){
    u[x]=1;
    for(int i=0;i<g[x].get_size();i++){
        int xn=g[x][i];
        if(u[xn]==0){
            dfs(xn);
        }
    }
}

int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int sol=0;
    for(int i=1;i<=n;i++){
        if(u[i]==0){
            sol++;
            dfs(i);
        }
    }
    fout<<sol<<"\n";
    return 0;
}