Cod sursa(job #2615920)

Utilizator suranimariaMaria Surani suranimaria Data 15 mai 2020 20:28:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
#define Nmax 100005

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

vector<int>v[Nmax] ;
int vizitat[Nmax] ;

void extindere( int nod )
{
    vizitat[nod] = 1 ;
    for ( auto i : v[nod] )
        if ( vizitat[i] == 0 )  extindere(i) ;
}


int main()
{
    int n , m , cont = 0 , x , y;
    fin >> n >> m ;
    for ( int i = 0 ; i < m ; i++ )
    {
        fin >> x >> y ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    for( int i = 1 ; i <= n ; i++ ) vizitat[i] = 0 ;
    for ( int i = 1 ; i <= n ; i++ )
        {
           if ( vizitat[i] == 0 )
                {
                    extindere(i) ;
                    cont++ ;
                }
        }
    fout << cont ;
    return 0;
}