Cod sursa(job #2280679)

Utilizator andonis1616And Cuz andonis1616 Data 10 noiembrie 2018 23:32:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>
#define NMAX 200005
using namespace std;
ifstream in ("dfs.in");
ofstream out ("dfs.out");

int n,m;
vector <int> muchii[NMAX];
bool vizitat[NMAX];
int answer;

void DFS(int x)
{
    vizitat[x]=true;
    int nod_curent;
    for(auto i=muchii[x].begin();i!=muchii[x].end();i++){
        nod_curent=*i;
        if(!vizitat[nod_curent]){
            DFS(nod_curent);
        }
    }
}

int main()
{
    int i,x,y;
    in>>n>>m;
    for(i=1;i<=m;i++){
        in>>x>>y;
        muchii[x].emplace_back(y);
        muchii[y].emplace_back(x);
    }
    for(i=1;i<=n;i++){
        if(!vizitat[i]){
            DFS(i);
            answer++;
        }
    }
    out<<answer;
    return 0;
}