Cod sursa(job #2199631)

Utilizator SpiristulTeribilStefan Vilcu SpiristulTeribil Data 28 aprilie 2018 15:56:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>

using namespace std;

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

const int N = 100001 ;
const int M = 200001 ;

int m , n , nr , lst[N] , vf[2*M] , urm[2*M] , viz[N] , comp ;

void adauga(int x , int y) {
    vf[++nr] = y ;
    urm[nr] = lst[x] ;
    lst[x] = nr ;
}

void dfs (int x) {
    viz[x] = comp ;
    int p = lst[x] , y ;
    while (p != 0) {
         y = vf[p] ;
         if ( !viz[y]) {
            dfs(y) ;
         }
         p = urm[p] ;
    }
}

int main()
{
     fin >> n >> m ;
     int x , y ;
     for ( int i = 0 ; i < m ; i++) {
          fin >> x >> y ;
          adauga (x , y) ;
          adauga (y , x) ;
     }
     for(int i = 1 ; i <= n ; i++)
        if(!viz[i]) {
            comp++ ;
            dfs(i) ;
        }
    fout << comp ;
    return 0 ;
}