Cod sursa(job #3250412)

Utilizator justann33Anita Gheboeanu justann33 Data 20 octombrie 2024 18:36:13
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
/*
 Se da un graf neorientat cu N noduri si M muchii.
 Sa se determine numarul componentelor conexe ale grafului.
 Fisierul de intrare dfs.in contine pe prima linie numerele N si M cu semnificatia din enunt, iar pe urmatoarele M linii se gasesc cate doua numere X si Y cu semnificatia: exista muchie de la nodul X la nodul Y.
 */
#define maxn 100010
ifstream f("dfs.in");
ofstream g("dfs.out");
bool viz[maxn];
void dfs(int nod, vector<vector<int>>& adiacernta){
    viz[nod]=1;
    for(auto urm: adiacernta[nod]){
        if(!viz[urm]){
            dfs(urm, adiacernta);
        }
    }
}
int main() {
    int n,m,Start,cc=0,x,y;
    f>>n>>m;
    vector<vector<int>> Lista(n+1);
    for(int i=1;i<=m;i++){
        f>>x>>y;
        Lista[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
        if(!viz[i]){
            dfs(i,Lista);
            cc++;
        }
    }
    g<<cc;
}