Cod sursa(job #2859573)

Utilizator oporanu.alexAlex Oporanu oporanu.alex Data 1 martie 2022 16:19:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
 #include <bits/stdc++.h>

using namespace std;

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

int main()
{   int V, E;

    fin >> V >> E;

    vector<vector<int>> adjList(V + 1, vector<int>());
    vector<int> vis(V + 1, false);
    for(int i = 1; i <= E; ++i) {
        int v1, v2;
        fin >> v1 >> v2;
        adjList[v1].push_back(v2);
        adjList[v2].push_back(v1);
    }

    int connectedComponents = 0;
    for(int i = 1; i <= V; ++i) {
        if(vis[i] == false) {
            ++connectedComponents;
            stack<int> recursionStack;
            recursionStack.push(i);

            while(!recursionStack.empty()) {
                int crt = recursionStack.top();
                recursionStack.pop();
                for(auto ngb: adjList[crt]) {
                    if(vis[ngb] == false) {
                        vis[ngb] = true;
                        recursionStack.push(ngb);
                    }
                }
            }
        }
    }

    fout << connectedComponents;


    return 0;
}