Cod sursa(job #2839143)

Utilizator raduonofreiRadu Onofrei raduonofrei Data 25 ianuarie 2022 13:18:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>
#define NMAX 100001

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

///matrice adiacenta
int n, m, start;
vector <int> A[NMAX];
int viz[NMAX];

int nrc;

void citire();
void DFS(int x);
void afisare();
int main()
{
 citire();
 for (int i=1; i<=n; i++) {
    if (!viz[i]) {
        nrc++;
        DFS(i);
    }
 }
 fout<<nrc<<'\n';
 return 0;
}

void citire() {
    int x, y;
    fin>>n>>m;
    for (int i=0; i<m; i++) {
        fin>>x>>y;
        A[x].push_back(y);
        A[y].push_back(x);
    }
}

void DFS(int x) {
    unsigned int i;
    viz[x] = nrc;
    ///parcurg vecinii lui x
    for(i=0; i<A[x].size(); i++)
        if (!viz[A[x][i]]) DFS(A[x][i]);
}