Cod sursa(job #3248586)

Utilizator bbogdiBogdan Jugastru bbogdi Data 12 octombrie 2024 10:49:13
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

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

vector<set<int>> graph;
int nrnodes, nredges, sourcenode;
vector<bool> visited;

void dfs(int currentNode){
    visited[currentNode]=true;
    for(int neighbour: graph[currentNode]){
        if(!visited[neighbour]){
            dfs(neighbour);
        }
    }
    fout<<currentNode<<" ";
    for(int l: graph[currentNode]){
        if(visited[l]!=1){
            dfs(l);
        }
    }
}

int main() {
    fin>>nrnodes>>nredges;
    graph= vector<set<int>>(nrnodes+1);
    visited = vector<bool>(nrnodes+1, false);
    int i, j;
    for(int k=0;k<=nredges+1;k++){
        fin>>i>>j;
        graph[i].insert(j);
        graph[j].insert(i);
    }
    int cont=0;
    for(int i=0;i<nrnodes;i++){
        if(!visit(i)){
            cont++;
            dfs(i);
        }
    }
    fout<<cont;
}