Cod sursa(job #3260429)

Utilizator juniorOvidiu Rosca junior Data 2 decembrie 2024 13:54:27
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>

using namespace std;

int n, m, cc, l, c, i; // noduri, muchii, componente conexe
bool a[2000][2000], v[2000];
ifstream fin("dfs.in");
ofstream fout("dfs.out");

void DFS(int nc) { // nodul curent
    int i;

    v[nc] = true;
    for (i = 1; i <= n; i++)         // pentru fiecare nod
        if (a[nc][i] and not v[i])  // i este vecin nevizitat al nodului curent?
            DFS(i);                  // Continuam parcurgerea in adancime.
}

int main() {
    fin >> n >> m;                // Se citeste numarul de noduri si numarul de muchii.
    for (i = 1; i <= m; i++) {    // Pentru fiecare muchie
        fin >> l >> c;            // Se citesc informatiile despre o muchie.
        a[l][c] = a[c][l] = true; // Se actualizeaza matricea de adiacenta
    }
    for (i = 1; i <= n; i++) {
        if (not v[i]) {
            cc++;
            DFS(i);
        }
    }
    fout << cc;
}