Cod sursa(job #2863407)

Utilizator dianannnDiana Novac dianannn Data 6 martie 2022 17:49:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
   #include <vector>
    using namespace std;
ifstream f ("dfs.in");
ofstream g ("dfs.out");
    vector <int> adj[100001];
    bool visited[100001];

    void dfs(int s) {
        visited[s] = true;
        for(int i = 0;i < adj[s].size();++i)    {
         if(visited[adj[s][i]] == false)
             dfs(adj[s][i]);
        }
    }

    void initialize() {
        for(int i = 0;i < 10;++i)
         visited[i] = false;
    }

    int main() {
        int nodes, edges, x, y, connectedComponents = 0;
        f>> nodes;                       //Number of nodes
        f >> edges;                       //Number of edges
        for(int i = 0;i < edges;++i) {
         f >> x >> y;
     //Undirected Graph
         adj[x].push_back(y);                   //Edge from vertex x to vertex y
         adj[y].push_back(x);                   //Edge from vertex y to vertex x
        }

        initialize();                           //Initialize all nodes as not visited

        for(int i = 1;i <= nodes;++i) {
         if(visited[i] == false)     {
             dfs(i);
             connectedComponents++;
         }
        }
        g<< connectedComponents << endl;
        return 0;
    }