Cod sursa(job #2153951)

Utilizator gabrielcatalinBrighila Gabriel Catalin gabrielcatalin Data 6 martie 2018 16:34:44
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("ninjago.in");
ofstream fout ("ninjago.out");
const unsigned NMAX = 31200;
int N , M , VIZITAT[NMAX] ;
vector < int > MUCHII [NMAX] ;
int insule ;

void citire()
{
    int i,x,y;
    fin >> N >> M ;
    for(i=1;i<=M;i++)
    {
        fin >> x >> y ;
        MUCHII[x].push_back(y);
        MUCHII[y].push_back(x);
    }

}

void DFS ( int NOD )
{
    VIZITAT [NOD] = 1;
    for ( int i = 0 ; i < MUCHII[NOD].size() ; i++ )
    {
        int vecin = MUCHII[NOD][i];
        if ( !VIZITAT [vecin] )
            DFS ( vecin ) ;
    }
}

int main()
{
    int i;
    citire();
    for(i=1;i<=N;i++)
        if( ! VIZITAT [i] )
    {
        DFS(i);
        insule++;
    }
    fout << insule ;
    return 0;
}