Cod sursa(job #2717063)

Utilizator AlexZeuVasile Alexandru AlexZeu Data 6 martie 2021 11:36:11
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int noduri, muchii, mt_adiacenta[10000][10000], fr[10000], ans;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

void DFS(int i) {
    if (fr[i] == 0) {
        fr[i] = 1;
        for (int j = 1; j <= noduri; ++j) {
            if (mt_adiacenta[i][j] == 1) {
                DFS(j);
                fr[j] = 1;
            }
        }
    }
}

int main() {
    fin >> noduri >> muchii;
    for (int i = 1; i <= muchii; ++i) {
        int x, y;
        fin >> x >> y;
        mt_adiacenta[x][y] = 1;
        mt_adiacenta[y][x] = 1;
    }
    for (int i = 1; i <= noduri; ++i) {
        if (fr[i] == 0) {
            DFS(i);
            ++ans;
        }
    }
    fout << ans;
    return 0;
}