Cod sursa(job #1596594)

Utilizator georgeliviuPereteanu George georgeliviu Data 11 februarie 2016 10:49:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>

using namespace std;

#define Nmax 100010
vector <int> ad[Nmax] ;
int n , m , x , y , cnt ;
bool b[Nmax] ;

void dfs ( int nod )
{
    if ( b[nod] ) return ;
    b[nod] = true ;
    for ( int i = 0 ; i < ad[nod].size() ; ++i )
        dfs(ad[nod][i]) ;
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    scanf("%d %d",&n,&m);
    for ( int i = 1 ; i <= m ; i++ )
    {
        scanf("%d %d",&x,&y);
        ad[x].push_back(y);
        ad[y].push_back(x) ;
    }
    for ( int i = 1 ; i <= n ; i++ )
    {
        if ( !b[i] )
        {
            cnt++;
            dfs(i) ;
        }
    }
    printf("%d ",cnt) ;
}