Cod sursa(job #2259688)

Utilizator alexbuzescuAlexandru Buzescu alexbuzescu Data 13 octombrie 2018 17:16:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector <int> Muchii[200000];
bool vizitat[200000];
unsigned int insule=0;
int n,m;
void DFS( int nod ){
    unsigned i;
    vizitat[nod]=true;
    for(i=0;i<Muchii[nod].size();i++){
        int vecin=Muchii[nod][i];
        if(!vizitat[vecin]){
            DFS(vecin);
        }
    }
}
void Citire(){
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        Muchii[x].push_back(y);
        Muchii[y].push_back(x);
    }
    for(i=1;i<=n;i++){
        if(!vizitat[i]){
            insule++;
            DFS(i);
        }
    }
}
int main()
{
    Citire();
    fout<<insule;
    return 0;
}