Cod sursa(job #2734853)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 1 aprilie 2021 15:12:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.66 kb
#include <fstream>

using namespace std;

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

const int nmax = 100000;

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];
        capacity = 1;
        v[0] = x;
        size = 1;
    } else if ( size == capacity ) {
        int *v_aux = new int[capacity*2];
        for ( int i = 0; i < size; ++ i ) {
            v_aux[i] = v[i];
        }
        delete[] v;
        v = v_aux;
        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 ( size > x ) {
        size = x;
    } else if ( size < x ) {
        if ( capacity < x ) {
            int *v_aux = new int[x];
            for ( int i = 0; i < size; ++ i ) {
                v_aux[i] = v[i];
            }
            delete[] v;
            v = v_aux;
            capacity = x;
        }
        size = x;
    }
}

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

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

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;
}