Cod sursa(job #3254413)

Utilizator ursus161Stefan Ghetu ursus161 Data 7 noiembrie 2024 16:06:32
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int N,M;
const int NMAX=100005;
bool vizitat[NMAX];
vector <int> muchii[NMAX];

int insule=0;

void dfs(int nod){

    vizitat[nod]=true;
    for(unsigned int i=0; i<muchii[nod].size(); i++)
    {
        int vecin=muchii[nod][i];
        if(!vizitat[vecin]) dfs(vecin);
    }

}


void citire(){
    fin>> N>> M;
    for(int i=1; i<=N;i++){
        int x,y;
        fin>>x>>y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }
    for(int i=1; i<=N; i++){
         if(!vizitat[i]){insule++; dfs(i);}

    }
}

int main()
{ citire();
fout<<insule<<" ";

    return 0;
}