Cod sursa(job #1090677)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 22 ianuarie 2014 22:19:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");

vector <int> l[100010];

int v[100010], i, nr , n , m, x, y;

void dfs (int nod) {
    v[nod]=1;
    for (int i=0;i<l[nod].size();i++)
        if (v[l[nod][i]]==0)
            dfs(l[nod][i]);
}

int main () {

    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }

    for (i=1;i<=n;i++)
        if (v[i]==0) {
            nr++;
            dfs(i);
        }

    fout<<nr<<"\n";

    return 0;
}