Cod sursa(job #1108268)

Utilizator gedicaAlpaca Gedit gedica Data 15 februarie 2014 15:29:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<vector>

using namespace std;

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

const int nmax= 100004;
vector <int> g[nmax+1];
bool dacanod[nmax+1]= {0};

void dfs( int a )
{
    dacanod[a]=1;
    for( int k= 0; k< g[a].size() ; k++ )
    {
        if( dacanod[ g[a][k] ] == 0) dfs( g[a][k] );
    }
}
int main(  )
{
    int n= 0, m= 0,i= 0;
    in>>n>>m;
    int x= 0,y= 0;
    for( i= 1 ; i<=m ; ++i )
    {
        in>>x>>y;
        g[x].push_back( y );
        g[y].push_back( x );
    }
    int sol= 0;
    for ( int i= 1; i<= n; ++i )
    {
        if ( dacanod[i] == 0 ) {
            dfs( i );
            ++sol;
        }
    }
    out<<sol<<'\n';
    in.close();
    out.close();
    return 0;
}