Cod sursa(job #1694834)

Utilizator CTI_KnightCir Constantin CTI_Knight Data 26 aprilie 2016 00:19:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
# include <fstream>
# include <algorithm>
# include <queue>
# include <vector>
# define SIZE 100005

using namespace std;

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

class Graf {
    int n, m;
    bool v[SIZE];
    vector < vector < int > > A;
public:
    Graf() {};
    ~Graf() {};
    void read();
    void set_viz();
    void DFS( int start );
    void solve();
};

void Graf :: read() {
    f >> n >> m;
    A.resize( n + 1 );
    for ( int i = 0; i < m; ++ i ) {
        int x, y; f >> x >> y;
        A[x].push_back( y );
        A[y].push_back( x );
    }
}

void Graf :: set_viz() {
    for ( int i = 0; i <= SIZE; ++ i ) {
        v[i] = false;
    }
}

void Graf :: DFS( int start ) {
    v[start] = true;
    for ( auto it: A[start] ) {
        if ( v[it] == 0 ) {
            DFS( it );
        }
    }
}

void Graf :: solve() {
    read();
    set_viz();
    int answer = 0;
    for ( int nod = 1; nod <= n; ++ nod ) {
        if ( v[nod] == 0 ) {
            ++ answer;
            DFS( nod );
        }
    }
    g << answer;
}

int main()
{
    Graf G;
    G.solve();

    return 0;
}