Cod sursa(job #2784539)

Utilizator bibiancapitu2004Pitu Bianca bibiancapitu2004 Data 16 octombrie 2021 17:51:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int DIMN = 100005;

vector<int> graf[DIMN];
bool viz[DIMN];

vector<int> componenta;
vector<vector<int>> toate_componentele;

void dfs(int nod, int parinte = 0) {
    viz[nod] = true;
    componenta.push_back(nod);
    for (int vecin : graf[nod]) {
        if (!viz[vecin]) {
            dfs(vecin, nod);
        }
    }
}
/*
void fun(vector<int> a) { // --> mereu va face o copie atunci cand se apeleaza
    // .....
}

void fun2(vector<int>& a) {
    // .....
}

void fun3(const vector<int>& a) {
    // .....
}
*/
int main() {
    int N, M;
    in >> N >> M;
    for (int i = 0; i < M; ++i) {
        int x, y;
        in >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    for (int i = 1; i <= N; ++i) {
        if (!viz[i]) {
            componenta.clear();
            dfs(i);
            toate_componentele.push_back(componenta);
        }
    }

    out << toate_componentele.size() << "\n";

    // for (vector<int>& c : toate_componentele)
    /* for (auto& c : toate_componentele) {
        for (int nod : c)
            out << nod << " ";
        out << "\n";
    } */

    // int a = 7;
    // int& b = a;
    // b++;
    return 0;

}