Cod sursa(job #1959233)

Utilizator vlasiuflaviusVlasiu Flavius vlasiuflavius Data 9 aprilie 2017 11:22:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <vector>
using namespace std;
ofstream fout ("dfs.out");
ifstream fin ("dfs.in");
int n,m,i,a,b,cnt;
vector < int > v[100005];
int rsp[100005];
void dfs( int nod , int val )
{
    rsp[ nod ] = val;
    for( auto it : v[ nod ] )
    {
        if( !rsp[ it ] )
            dfs( it , val );
    }
}
int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>a>>b;
        v[ a ].push_back( b );
        v[ b ].push_back( a );
    }
    for( i = 1 ; i <= n ; i++ )
    {
        if( !rsp[ i ] )
            dfs( i , ++cnt );
    }
    fout<<cnt;
}