Cod sursa(job #2167531)

Utilizator chioreanraulChiorean Raul chioreanraul Data 13 martie 2018 22:09:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>

using namespace std;
int n,m,i,j,nrconex,sc[100005];

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

vector < int > v[100005];

void dfs( int nod )
{
    sc[ nod ] = nrconex;
    for( int k = 0; k < v[ nod ].size( ); k++ )
    {
         if( sc[ v[ nod ][ k ] ] == 0 )
            dfs( v[ nod ][ k ] );
    }
}
int main()
{
    fin>>n>>m;
    for( int r = 1; r <= m; r++ )
    {
        fin>>i>>j;
        v[ i ].push_back( j );
        v[ j ].push_back( i );
    }
    for( int j = 1; j <= n; j++ )
    {
        if( sc[ j ] == 0 )
        {
            nrconex++;
            dfs( j );
        }
    }
    fout<<nrconex;
    return 0;
}