Cod sursa(job #3156972)

Utilizator JohnnyFortaPascu Ioan JohnnyForta Data 13 octombrie 2023 22:10:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

list<pair<int,int>> * readEdges(int& n, int& m, ifstream & in){
    //dynamically allocate a list of pairs
    list<pair<int,int>> * E = new list<pair<int,int>>;
    //read dimentions
    in>>n>>m;
    int x, y;
    //read edges
    while(in>>x>>y){
        E->push_back(pair<int,int>(x,y));
    }
    //return the list
    return E;
}

vector<list<int>> * edgesToList(list<pair<int,int>> * E, int n,bool directed){
    //create a vector of lists
    vector<list<int>> * L = new vector<list<int>>;
    //set the vector's length to the number of nodes
    L->resize(n);
    //traverse the list of edges and add them to the adjacency lists
    for(auto p : *E){
        (*L)[p.first - 1].push_back(p.second);
        if(!directed){
            (*L)[p.second - 1].push_back(p.first);
        }
    }
    //return the lists
    return L;
}

void printList(vector<list<int>> * L){
    for(int i = 0; i < (*L).size(); i++){
        cout<<i + 1<<" : ";
        for(auto p : (*L)[i]){
            cout<<p<<" ";
        }
        cout<<endl;
    }
}


void DFSInner(vector<list<int>> * L, int n, int current, bool * visited){
    //"visit" the current node
    visited[current - 1] = true;
    //traverse the neighbours of the current node
    for(auto x : (*L)[current - 1]){
        if(!visited[x - 1]){
            //visit the neighbour
            visited[x - 1] = true;
            DFSInner(L, n, x, visited);
        }
    }
}

int main(){
    int n, m, nrComponente = 0;
    ifstream f("dfs.in");
    ofstream o("dfs.out");
    list<pair<int, int>> * E = readEdges(n, m, f);
    vector<list<int>> * L = edgesToList(E, n, false);

    bool * visited = new bool[n];
    for(int i = 0; i < n; i++){
        visited[i] = false;
    }

    for(int i = 0; i < n; i++){
        if(!visited[i]){
            nrComponente ++;
            DFSInner(L, n, i + 1, visited);
        }
    }

    o<<nrComponente;
    f.close();
    o.close();
}