Cod sursa(job #3242917)

Utilizator cristian46290Petre Cristian cristian46290 Data 14 septembrie 2024 16:53:50
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int n, m, k;
int x, y;
bool vizitat[105];
vector < int > muchii[105];

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

int main()
{
    f >> n >> m;
    for (int i = 1;i <= m;i++){
        f >> x >> y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }
    int insule = 0;
    for (int i = 1;i <= n;i++){
        if (!vizitat[i]){
            dfs(i);
            insule++;
        }
    }
    g << insule;
}