Cod sursa(job #2276982)

Utilizator maria15Maria Dinca maria15 Data 5 noiembrie 2018 18:00:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <vector>

using namespace std;

int n, m, i, f[100002], a, b, nr;
vector<int> v[100002];

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

void dfs(int nod){
    for(int j = 0;j<v[nod].size();j++){
        int crt = v[nod][j];
        if(f[crt] == 0){
            f[crt] = f[nod];
            dfs(crt);
        }
    }
}

int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;i++)
        if(f[i] == 0){
            f[i] = ++nr;
            dfs(i);
        }
    fout<<nr;
    return 0;
}