Cod sursa(job #1319571)

Utilizator mambojamboPop Flaviu mambojambo Data 17 ianuarie 2015 09:49:32
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;

int n, m, x, y, comps = 0;
bool seen[nmax];
vector <int> v[nmax];

void dfs(int x) {
    seen[x] = true;

    for(int i=0; i<v[x].size(); i++) {
        int y = v[x][i];
        if(!seen[y]) dfs(y);
    }
}

int main() {
    ifstream f("dfs.in");
    ofstream g("dfs.out");

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

/*
    for(int x=1; x<=n; x++) {
        cout<<"Vecinii lui "<<x<<" sunt: ";

        for(int i=0; i<v[x].size(); i++)
            cout<<v[x][i]<<" ";
        cout<<"\n";
    }
*/

    for(int i=1; i<=n; i++)
        if(!seen[i])
            ++comps,
            dfs(i);

    g<<comps<<"\n";
    return 0;
}