Cod sursa(job #1505088)

Utilizator HarrisZambo Harris Harris Data 18 octombrie 2015 18:49:16
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <vector>
using namespace std;

fstream fin("dfs.in", ios::in);
fstream fout("dfs.out", ios::out);

vector <int> g[100005];
int i, n, m;

void citire(){
    int x, y;
    fin >> n >> m;
    for(i = 1; i <= n; i++)
        g[i].push_back(0);
    for(i = 1; i <= m; i++){
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void DFS(int k){
    g[k][0] = 1;
    for(i = 1; i < g[k].size(); i++){
        int vecin = g[k][i];
        if(!g[vecin][0])
            DFS(vecin);
    }
}

int main(){
    int c = 0;
    citire();
    for(i = 1; i <= n; i++)
        if(!g[i][0]){
            c++;
            DFS(i);
        }
    fout << c << '\n';
}