Cod sursa(job #2734936)

Utilizator GligarEsterabadeyan Hadi Gligar Data 1 aprilie 2021 17:38:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>

using namespace std;

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

struct vint{
    int *v=nullptr;
    int capacity=0, size=0;

    void push_back(int x);
    void pop_back();
    void resize(int x);
    void resize(int x, int y);
    void shrink_to_fit();
};

void vint::push_back(int x){
    if(v==nullptr){
        v=new int[1];
        v[0]=x;
        size++;
        capacity=1;
    }else if(capacity==size){
        int *v2=new int[capacity*2];
        for(int i=0;i<size;i++){
            v2[i]=v[i];
        }
        delete[] v;
        v=v2;
        capacity*=2;
        v[size]=x;
        size++;
    }else{
        v[size]=x;
        size++;
    }
}

void vint::pop_back(){
    if(size>0){
        size--;
    }
}

void vint::resize(int x){
    if(capacity<x){
        capacity=x;
        int *v2=new int[capacity];
        for(int i=0;i<size;i++){
            v2[i]=v[i];
        }
        delete[] v;
        v=v2;
    }
    size=x;
}

void vint::resize(int x, int y){
    if(capacity<x){
        capacity=x;
        int *v2=new int[capacity];
        for(int i=0;i<size;i++){
            v2[i]=v[i];
        }
        delete[] v;
        v=v2;
    }
    for(int i=size;i<x;i++){
        v[i]=y;
    }
    size=x;
}

void vint::shrink_to_fit(){
    capacity=size;
    int *v2=new int[size];
    for(int i=0;i<size;i++){
        v2[i]=v[i];
    }
    delete[] v;
    v=v2;
}

const int nmax=100000;

vint g[nmax+1];

bool u[nmax+1];

void dfs(int x){
    u[x]=1;
    for(int i=0;i<g[x].size;i++){
        int xn=g[x].v[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);
    }
    for(int i=1;i<=n;i++){
        g[i].shrink_to_fit();
    }
    int sol=0;
    for(int i=1;i<=n;i++){
        if(u[i]==0){
            sol++;
            dfs(i);
        }
    }
    fout<<sol<<"\n";
    return 0;
}