Cod sursa(job #1891565)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 24 februarie 2017 09:50:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
///FLAVIUS, UBESTE-MA
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector< int > G[100010];
int ans,use[100010],i,j,n,m,x,y,s;
queue <int> Q;

void DFS( int nod )
{
    use[ nod ] = 1;
    for( auto it : G[ nod ] )
        if( !use[ it ] )
            DFS( it );
}

int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y;
        G[ x ].push_back( y );
        G[ y ].push_back( x );
    }

    for( i = 1 ; i <= n ; i++ )
    {
        if( !use[ i ] )
        {
            DFS( i );
            ++ans;
        }
    }

    fout<<ans;

    return 0;
}