Cod sursa(job #2777193)

Utilizator Albert_GAlbert G Albert_G Data 22 septembrie 2021 16:11:37
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int N = 1e5+1;
int n,m;
vector<int> g[N+1];
bool visited[N+1];

void dfs(int i){
    visited[i] = 1;
    for(auto nod : g[i]){
        if(!visited[nod]){
            dfs(nod);
        }
    }
}

int main()
{
    in>>n>>m;
    in.close();
    for(int i=0;i<m;++i){
        int a,b;
        in>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int nc=0;
    for(int i=0;i<n;++i){
        if(!visited[i]){
            ++nc;
            dfs(i);
        }
    }
    out<<nc;
    out.close();
    return 0;
}